3. Gramatyki bezkontekstowe
3.1. Rozbiór gramatyczny
Niech będzie dana gramatyka bezkontekstowa G = .
Gramatyki rekursywne
Gramatykę nazywamy rekursywną, jeżeli w gramatyce tej możliwe jest wyprowadzenie
A ⇒+ αAβ dla pewnego nieterminala A ∈ N, przy czym α, β ∈ (N∪T)*.
Gramatykę nazywamy lewostronnie rekursywną, jeżeli w gramatyce tej możliwe jest
wyprowadzenie A ⇒+ Aβ dla pewnego nieterminala A ∈ N, przy czym β ∈ (N∪T)*.
Gramatykę nazywamy prawostronnie rekursywną, jeżeli w gramatyce tej możliwe jest
wyprowadzenie A ⇒+ αA dla pewnego nieterminala A ∈ N, przy czym α ∈ (N∪T)*.
Jeżeli język L(G) jest zbiorem nieskończonym, to jego gramatyka G musi być gramatyką
rekursywną.
Frazy
Łańcuch δ nazywamy frazą formy zdaniowej ω = αδβ dla symbolu nieterminalnego
A ∈ N, wtedy i tylko wtedy, gdy:
(i)
Z ⇒* αAβ
(ii)
A ⇒+ δ
przy czym α, δ, β ∈ (N∪T)*.
Łańcuch δ nazywamy frazą prostą formy zdaniowej ω = αδβ dla symbolu nieterminalnego
A ∈ N, wtedy i tylko wtedy, gdy:
(i)
Z ⇒* αAβ
(ii)
A⇒ δ
przy czym α, δ, β ∈ (N∪T)*.
Osnową formy zdaniowej jest najbardziej na lewo położona fraza prosta (to ostatnie,
określenie ma sens w przypadku gramatyk jednoznacznych – patrz dalej).
Wyprowadzenia lewostronne i prawostronne
Forma zdaniowa ψ jest wyprowadzalna bezpośrednio lewostronnie z formy zdaniowej ω w
gramatyce G, co zapisujemy
ω ⇒GL ψ
jeżeli:
ω ⇒G ψ
ω = γαδ
ψ = γβδ
(α → β) ∈ P
γ ∈ T*
α, β, δ, ψ, ω ∈ (N∪T)*
Powyższa definicja nie jest ukierunkowana jedynie na gramatyki bezkontekstowe, ale w
wyprowadzeniu lewostronnym w gramatyce bezkontekstowej zawsze skrajny lewy
nieterminal jest zastępowany prawą stroną pewnej produkcji.
Forma zdaniowa ψ jest wyprowadzalna bezpośrednio prawostronnie z formy zdaniowej ω
w gramatyce G, co zapisujemy
ω ⇒GP ψ
jeżeli:
ω ⇒G ψ
ω = γαδ
ψ = γβδ
(α → β) ∈ P
δ ∈ T*
α, β, γ, ψ, ω ∈ (N∪T)*
Podobnie jak poprzednio, powyższa definicja nie jest ukierunkowana jedynie na gramatyki
bezkontekstowe, ale w wyprowadzeniu prawostronnym w gramatyce bezkontekstowej zawsze
skrajny prawy nieterminal jest zastępowany prawą stroną pewnej produkcji.
Podobnie jak poprzednio, definiuje się relacje ⇒GL+, ⇒GL*, ⇒GP+, ⇒GP*, które są
odpowiednio przechodnim oraz przechodnim i zwrotnym domknięciem relacji bezpośredniej
wyprowadzalności lewostronnej ⇒GL i prawostronnej ⇒GP. Jeżeli wiadomo, o jaką
gramatykę chodzi, pomijamy dolny indeks „G” w oznaczeniu tych relacji pisząc po prostu:
⇒L+, ⇒L*, ⇒P+, ⇒P*, ⇒L oraz ⇒P.
Przykład:
Niech będzie dana gramatyka bezkontekstowa G = , gdzie:
N = {E, T, F}
T = {a, +, *, (, )}
P = { E → E+T | T
T → T*F | F
F → (E) | a
}
Z=E
Formą zdaniową w tej gramatyce jest np. łańcuch:
a+F*T
gdyż:
E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ a+T ⇒ a+T*F
Powyższe wyprowadzenie polegało na każdorazowym zastępowaniu skrajnego lewego
nieterminala prawą stroną jakiejś odpowiedniej produkcji, więc każdy krok tego
wyprowadzenia jest wyprowadzeniem lewostronnym. Możemy więc powiedzieć, że
rozpatrywany łańcuch jest formą zdaniową wyprowadzalną lewostronnie.
E
... zobacz całą notatkę
Komentarze użytkowników (0)