Język generowany przez gramatykę
Zbiór wszystkich ciągów, które można wyprowadzić z gramatyki, nazywany jest językiem wygenerowanym na podstawie tej gramatyki. Język generowany przez gramatykęG jest podzbiorem formalnie zdefiniowanym przez
L (G) = {W | W ∈ ∑ *, S ⇒ G W}
Jeśli L(G1) = L(G2), Gramatyka G1 jest odpowiednikiem gramatyki G2.
Przykład
Jeśli jest gramatyka
G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}
Tutaj S produkuje ABi możemy wymienić A przez a, i B przez b. Tutaj jedynym akceptowanym ciągiem jestabtj.
L (G) = {ab}
Przykład
Załóżmy, że mamy następującą gramatykę -
G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA | a, B → bB | b}
Język wygenerowany przez tę gramatykę -
L (G) = {ab, a 2 b, ab 2 , a 2 b 2 , ………}
= {a m b n | m ≥ 1 in ≥ 1}
Konstrukcja gramatyki generującej język
Rozważymy niektóre języki i przekonwertujemy je na gramatykę G, która tworzy te języki.
Przykład
Problem- Załóżmy, że L (G) = {a m b n | m ≥ 0 in> 0}. Musimy poznać gramatykęG który produkuje L(G).
Solution
Ponieważ L (G) = {a m b n | m ≥ 0 in> 0}
zbiór zaakceptowanych ciągów można przepisać jako -
L (G) = {b, ab, bb, aab, abb, …….}
W tym przypadku symbol początkowy musi mieć co najmniej jedno „b” poprzedzone dowolną liczbą „a”, w tym zero.
Aby zaakceptować zestaw ciągów {b, ab, bb, aab, abb, …….}, Wzięliśmy produkcje -
S → aS, S → B, B → b i B → bB
S → B → b (zaakceptowano)
S → B → bB → bb (zaakceptowano)
S → aS → aB → ab (zaakceptowano)
S → aS → aaS → aaB → aab (zaakceptowano)
S → aS → aB → abB → abb (Zaakceptowano)
W ten sposób możemy udowodnić, że każdy pojedynczy ciąg w L (G) jest akceptowany przez język generowany przez zbiór produkcyjny.
Stąd gramatyka -
G: ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB})
Przykład
Problem- Załóżmy, że L (G) = {a m b n | m> 0 i n ≥ 0}. Musimy znaleźć gramatykę G, która daje L (G).
Solution -
Ponieważ L (G) = {a m b n | m> 0 i n ≥ 0}, zbiór akceptowanych ciągów można przepisać jako -
L (G) = {a, aa, ab, aaa, aab, abb, …….}
W tym przypadku symbol początkowy musi mieć co najmniej jedno „a”, po którym następuje dowolna liczba „b”, w tym null.
Aby zaakceptować zestaw ciągów {a, aa, ab, aaa, aab, abb, …….}, Wzięliśmy produkcje -
S → aA, A → aA, A → B, B → bB, B → λ
S → aA → aB → aλ → a (zaakceptowano)
S → aA → aaA → aaB → aaλ → aa (zaakceptowano)
S → aA → aB → abB → abλ → ab (zaakceptowano)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (zaakceptowano)
S → aA → aaA → aaB → aabB → aabλ → aab (zaakceptowano)
S → aA → aB → abB → abbB → abbλ → abb (zaakceptowano)
W ten sposób możemy udowodnić, że każdy pojedynczy ciąg w L (G) jest akceptowany przez język generowany przez zbiór produkcyjny.
Stąd gramatyka -
G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB})