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})