J”ezyki, Automaty i Obliczenia. Odcinek 4

Automaty ze stosem. Własności jȩzyków bezkontekstowych

Damian Niwiński Listopad 1996

1 Automaty ze stosem

1.1 Podstawowe definicje

Automat ze stosem może być przedstawiony jako nast_{}epuj _{}acy układ:

A = (Σ, Γ, Q, q_{I}, Z_{I}, δ, F)

gdzie • Σ jest alfabetem symboli wejściowych,

• Γ jest alfabetem symboli stosowych,

• Q jest zbiorem stanów,

• q_{I} ∈ Q jest stanem pocz _{}atkowym,

• Z_{I} ∈ Γ jest symbolem startowym,

• δ ⊆ Q × (Σ ∪ {ϵ}) × Γ × Q × Γ^{∗} jest relacj _{}a przejścia,

• F ⊆ Q jest zbiorem stanów akceptuj _{}acych. Wszystkie wyst_{}epuj _{}ace tu zbiory s _{}a skończone.

Przejście postaci (q, a, Z, q′, γ) b_{}edziemy także zapisywać

q, a, Z →_{A} q′, γ

Należy je rozumieć nast_{}epuj _{}aco:

Gdy a ∈ Σ :

Jeżeli automat znajduje si_{}e w stanie q, głowica automatu czyta na taśmie symbol a, a na wierzchołku stosu znajduje si_{}e symbol Z, to w nast_{}epnej chwili czasu automat może zmienić stan na q′, zast _{}apić symbol Z na stosie przez słowo γ i przesun _{}ać głowic_{}e o jedno miejsce w prawo.

Gdy a = ϵ :

Jeżeli automat znajduje si_{}e w stanie q, a na wierzchołku stosu jest symbol Z, to w nast_{}epnej chwili automat może zmienić stan na q′ i zast _{}apić symbol Z na stosie przez słowo γ. Pozycja głowicy pozostaje przy tym nie zmieniona.

Zauważmy, że jeśli w rozważanym powyżej przejściu γ = Z′Z, to operacj_{}e na stosie można określić jako

połóż Z′ na stos,

a jeśli γ = ϵ, to jako

zdejmij symbol z wierzchołka stosu.^{1}

Konfiguracj_{}e automatu w danej chwili czasu możemy przedstawić jako trójk_{}e (q, w, γ), gdzie q ∈ Q, w ∈ Σ^{∗}, γ ∈ Γ^{∗}. Należy przez to rozumieć sytuacj_{}e, kiedy automat znajduje si_{}e w stanie q, w jest słowem, jakie pozostało jeszcze do przeczytania, a γ jest zawartości _{}a stosu, przy czym przyjmujemy, że pierwsza litera słowa γ odpowiada symbolowi na wierzchołku stosu itd.

Za konfiguracj_{}e pocz _{}atkow _{}a uważamy każd _{}a konfiguracj_{}e postaci

(q_{I}, w, Z_{I})

1Można wykazać, że automaty ze stosem używaj _{}ace jedynie tych dwóch operacji maj _{}a nie mniejsz _{}a sił_{}e obliczeniow _{}a niż zdefiniowane przez nas bardziej ogólne automaty.

natomiast konfiguracj _{}a końcow _{}a nazwiemy dowoln _{}a konfiguracj_{}e postaci (q, ϵ, γ) (tzn. kiedy całe słowo zostało już przeczytane). Dalej, określamy relacj_{}e na konfiguracjach

(q, w, γ) ⊢_{A} (q′, w′, γ′)

odzwierciedlaj _{}ac _{}a fakt, że konfiguracja (q′, w′, γ′) może być osi _{}agni_{}eta z konfiguracji (q, w, γ) w jednym kroku przez wykonanie jakiegoś przejścia automatu A.

Mianowicie, relacja

(q, aw, Zβ) ⊢_{A} (q′, w, αβ)

zachodzi, o ile

q, a, Z →_{A} q′, α

jest przejściem automatu A. Zauważmy, że trójka (q, w, ϵ) (pusty stos) jest dobrze określon _{}a konfiguracj _{}a, z której jednak nie ma przejścia do żadnej konfiguracji.

Jak zwykle, ⊢_{A}^{∗} oznacza zwrotno-przechodnie domkni_{}ecie relacji ⊢_{A}.

Niech teraz w ∈ Σ^{∗}. Ci _{}ag konfiguracji (q_{0}, w_{0}, γ_{0}), (q_{1}, w_{1}, γ_{1}), …, (q_{m}, w_{m}, γ_{m}), gdzie (q_{0}, w_{0}, γ_{0}) jest konfiguracj _{}a pocz _{}atkow _{}a z w_{0} = w oraz, dla i < m, (q_{i}, w_{i}, γ_{i}) ⊢_{A} (q_{i+1}, w_{i+1}, γ_{i+1}), nazywamy obliczeniem automatu A na słowie w. Obliczenie nazwiemy akceptuj _{}acym jeśli (q_{m}, w_{m}, γ_{m}) jest konfiguracj _{}a końcow _{}a (tj. w_{m} = ϵ), a ponadto q_{m} ∈ F. J_{}ezyk rozpoznawany przez automat ze stosem A określamy jako zbiór tych słów, dla których istnieje obliczenie akceptuj _{}ace; tak wi_{}ec

L(A) = {w ∈ Σ^{∗} : (q_{I}, w, Z_{I}) ⊢_{A}^{∗}(q_{f}, ϵ, γ) dla pewnych q_{f} ∈ F, γ ∈ Γ^{∗}}

1.2 Automaty akceptuj _{}ace przez opróżnienie stosu

Dla automatu ze stosem A, określamy j_{}ezyk Z(A) obejmuj _{}acy te i tylko te słowa w, dla których istnieje obliczenie zakończone całkowitym opróżnieniem stosu,

Z(A) = {w ∈ Σ^{∗} : (q_{I}, w, Z_{I}) ⊢_{A}^{∗}(q, ϵ, ϵ) dla pewnego q ∈ Q}

W ten sposób przyporz _{}adkowujemy automatowi j_{}ezyk na ogół różny od L(A), przy czym stany akceptuj _{}ace nie odgrywaj _{}a tutaj żadnej roli. Okazuje si_{}e jednak, że nowy sposób akceptacji jest w pewnym sensie równoważny poprzedniemu.

Fakt 1 1. Dla każdego automatu ze stosem A, istnieje automat ze stosem A′, taki że L(A) = Z(A′).

2. Dla każdego automatu ze stosem B, istnieje automat ze stosem B′, taki że Z(B) = L(B′).

Dowód. Ad (1). Niech A = (Σ, Γ, Q, q_{I}, Z_{I}, δ, F). Określamy automat

A′ = (Σ, Γ ∪ {Z′_{I}}, Q ∪ {q′_{I}, q_{e}}, q′_{I}, Z′_{I}, δ′, ∅)

gdzie δ′ ⊇ δ jest rozszerzeniem δ o nast_{}epuj _{}ace przejścia

q′_{I}, ϵ, Z′_{I} → q_{I}, Z_{I}Z′_{I}
q_{f}, ϵ, Z → q_{e}, Z  dla q_{f} ∈ F, Z ∈ Γ ∪ {Z′_{I}}
q_{e}, ϵ, Z → q_{e}, ϵ  dla Z ∈ Γ ∪ {Z′_{I}}

A zatem, automat A′ rozpoczyna działanie od położenia “starego” symbolu startowego Z_{I} na “nowy” symbol Z′_{I}. Nast_{}epnie automat A′ symuluje działanie automatu A, z tym, że kiedy A wchodzi w stan akceptuj _{}acy, A′ może niedeterministycznie przyj _{}ać opcj_{}e (całkowitego) opróżniania stosu. Zanim to nast _{}api, nowy symbol startowy pozostaje cały czas na dnie stosu, żeby unikn _{}ać przypadkowej akceptcji przez A′ w sytuacji kiedy A opróżnia stos bez wejścia w stan akceptuj _{}acy.

Szczegóły dowodu, że L(A) = L(A′) pozostawiamy Czytelnikowi.

Ad (2). Niech B = (Σ, Γ, Q, q_{I}, Z_{I}, δ, ∅). Określamy automat

B′ = (Σ, Γ ∪ {Z′_{I}}, Q ∪ {q′_{I}, q_{f}}, q′_{I}, Z′_{I}, δ′, {q_{f}})

gdzie δ′ ⊇ δ jest rozszerzeniem δ o nast_{}epuj _{}ace przejścia

\begin{aligned}q′_{I}, ϵ, Z′_{I} & → & q_{I}, Z_{I}Z′_{I} \\ q, ϵ, Z′_{I} & → & q_{f}, ϵ & dla q ∈ Q \end{aligned}

Intuicyjnie, automat B′ symuluje działanie automatu B, z tym że na spodzie stosu pozostaje cały czas nowy symbol startowy Z′_{I}, który poza tym nie jest używany. Jeśli w pewnej chwili obliczenia symbol ten znajdzie si_{}e na wierzchołku stosu, oznacza to, że automat B, w odnośnej chwili symulowanego obliczenia opróżniłby swój stos. Dlatego automat B′ wchodzi wówczas w stan akceptuj _{}acy. Pami_{}etajmy jednak, że do tego, by obliczenie było akceptuj _{}ace nie wystarczy samo pojawienie si_{}e stanu akceptuj _{}acego, potrzeba jeszcze, by konfiguracja była końcowa (tzn. by całe słowo zostało przeczytane). □

Ćwiczenia

1. Skonstruować automaty ze stosem rozpoznaj _{}ace poznane wcześniej j_{}ezyki bezkontekstowe: zbiór palindromów, zbiór poprawnie uformowanych ci _{}agów nawiasów, zbiór słów, które maj _{}a dwa razy wi_{}ecej b niż a, zbiór ci _{}agów, które nie s _{}a postaci ww.

2. Dla liczby naturalnej n, niech bin(n) ∈ {0, 1}^{∗} b_{}edzie binarnym przedstawieniem liczby n. Skonstruować automat ze stosem rozpoznaj _{}acy j_{}ezyk

{bin(n)$bin(n + 1)^{R} : n ∈ N}

3. Dowieść, że dla każdego automatu ze stosem A, można skonstruować automat ze stosem o dwóch stanach A′, taki że L(A) = L(A′).

4. Dowieść, że automatowi A′ z poprzedniego zadania można postawić dalszy wymóg, że każde przejście jest postaci

q, a, Z →_{A′} q′, α

gdzie |α| ≤ 2 (q, q′ dowolne).

5. Dowieść, że dla każdego automatu ze stosem A, można skonstruować równoważny mu automat ze stosem A′′, w którym każde przejście jest postaci

q, a, Z →_{A′′} q′, Y Z

lub

q, a, Z →_{A′′} q′, ϵ

(*) Czy dla tego automatu można nadal ograniczyć liczb_{}e stanów?

6. Maj _{}ac dany automat ze stosem akceptuj _{}acy j_{}ezyk L, skonstruować automaty ze stosem akceptuj _{}ace nast_{}epuj _{}ace j_{}ezyki:

• Prefix(L) = {w : (∃v)wv ∈ L}

• Suffix(L) = {w : (∃u)uw ∈ L}

• Subword(L) = {w : (∃u, v)uwv ∈ L}

• (*) L^{R} = {w^{R} : w ∈ L}

7. Maj _{}ac dany automat ze stosem akceptuj _{}acy j_{}ezyk L i automat skończony akceptuj _{}acy j_{}ezyk R, skonstruować automaty ze stosem akceptuj _{}ace nast_{}epuj _{}ace j_{}ezyki:

• LR^{−1}

• R^{−1}L

• L ∩ R

8. Dla danych j_{}ezykow regularnych L i M, skonstruować automat ze stosem rozpoznaj _{}acy j_{}ezyk ⋃_{i∈N}(L^{i} ∩ M^{i}). Podać przykład, że zbiór ten nie musi być regularny.

9. (*) Dowieść, że dla każdego automatu ze stosem A istnieje stała C (zależna od automatu), taka, że dla każdego słowa w ∈ Z(A), istnieje obliczenie akceptuj _{}ace (przez pusty stos) o długości ≤ C|w|. Wskazówka: oszacować wysokość stosu w obliczeniu akceptuj _{}acym.

10. (*) Niech A b_{}edzie automatem ze stosem. Dowieść, że zbiór słów, które s _{}a możliwymi zawartościami stosu automatu A, jest j_{}ezykiem regularnym. Formalnie, mamy na myśli zbiór

{α ∈ Γ^{∗} : (∃w, v ∈ Σ^{∗})(∃q ∈ Q) q_{I}, w, Z_{I} ⊢_{A} q, v, α}

Wywnioskować st _{}ad, że zbiór słów, które s _{}a możliwymi zawartościami stosu automatu A w jakimś obliczeniu akceptuj _{}acym, jest j_{}ezykiem bezkontekstowym.

11. Automat ze stosem A = (Σ, Γ, Q, q_{I}, Z_{I}, δ, F) nazywamy deterministycznym, jeśli w każdej sytuacji możliwy jest co najwyżej jeden ruch. Dokładniej:

• jeśli, dla pewnej pary q, Z, zachodzi q, ϵ, Z →_{A} p, α przy pewnych p, α, to dla żadnego σ ∈ Σ, nie zachodzi q, σ, Z →_{A} p′, α′, dla żadnych p′, α′;

• dla każdych q, σ, Z, istnieje co najwyżej jedna para p, α, taka że q, σ, Z →_{A} p, α.

Niech L b_{}edzie zbiorem palindromów nad alfabetem {a, b}. Dowieść, że jeśli L = Z(A), to automat A jest niedeterministyczny. (Uwaga: analogiczny fakt można dowieść, gdy L = L(A), ale jest to znacznie trudniejsze.)

12. (**) Niech

M = {a^{n}b^{n} : n ∈ N} ∪ {a^{n}b^{2n} : n ∈ N}

Nietrudno jest podać niedeterministyczny automat ze stosem rozpoznaj _{}acy ten j_{}ezyk. Wykazać, że nie istnieje deterministyczny automat ze stosem A, taki, że M = L(A).

2 Automaty ze stosem jako modele rozpoznawania j_{}ezyków bezkontekstowych

W tym rozdziale wykażemy ścisł _{}a odpowiedniość pomi_{}edzy automatami ze stosem a gramatykami bezkontekstowymi : automaty rozpoznaj _{}a dokładnie te j_{}ezyki, które gramatyki generuj _{}a. Zanim pokażemy właściw _{}a konstrukcj_{}e, która automatowi przyporz _{}adkowuje równoważn _{}a gramatyk_{}e i na odwrót, wykażemy pewn _{}a nieco zaskakuj _{}ac _{}a a bardzo przydatn _{}a własność automatów ze stosem.

2.1 Redukcja stanów w automacie ze stosem

Udowodnimy, że, w automacie ze stosem, symbole stosowe mog _{}a w pewnym sensie całkowicie przej _{}ać rol_{}e stanów.

Twierdzenie 1 Dla każdego automatu ze stosem A istnieje automat A′ z jednym stanem, taki że Z(A) = Z(A′).

Dowód. Niech A = (Σ, Γ, Q, q_{I}, Z_{I}, δ, F). Określimy automat

A′ = (Σ, Γ′, {e}, e, Z′_{I}, δ′, ∅)

Nowym alfabetem symboli stosowych jest

Γ′ = {[q, Z, q′] : q, q′ ∈ Q, Z ∈ Γ} ∪ {Z′_{I}}

Zbiór przejść δ′ określony jest nast_{}epuj _{}aco:

• dla dowolnego q ∈ Q,

e, ϵ, Z′_{I} →_{A′} e, [q_{I}, Z_{I}, q]

jest przejściem automatu A′;

• o ile q, a, Z →_{A} p, Z_{1}Z_{2} … Z_{m}, m ≥ 1, jest przejściem automatu A, a p_{1}, p_{2}, …, p_{m−1}, q′ ∈ Q s _{}a dowolne, to

e, a, [q, Z, q′] →_{A′} e, [p, Z_{1}, p_{1}][p_{1}, Z_{2}, p_{2}] … [p_{m−2}, Z_{m−1}, p_{m−1}][p_{m−1}, Z_{m}, q′]

jest przejściem automatu A′; • o ile q, a, Z →_{A} q′, ϵ jest przejściem automatu A, to

e, a, [q, Z, q′] →_{A′} e, ϵ

jest przejściem automatu A′.

Wykażemy, że dla dowolnego w = uv, nast_{}epuj _{}ace warunki s _{}a równoważne:

Warunek 1

q_{I}, w, Z_{I} ⊢_{A}^{∗} q, v, Z_{1} … Z_{m}

Warunek 2 Dla dowolnych p_{1}, …, p_{m} ∈ Q,

e, w, Z′_{I} ⊢_{A′}^{∗} e, v, [q, Z_{1}, p_{1}][p_{1}, Z_{2}, p_{2}] … [p_{m−2}, Z_{m−1}, p_{m−1}][p_{m−1}, Z_{m}, p_{m}]

Zauważmy od razu, że dla v = ϵ i m = 0, z równoważności Warunków 1 i 2 otrzymamy, że

q_{I}, w, Z_{I} ⊢_{A}^{∗} q, ϵ, ϵ ⟺ e, w, Z′_{I} ⊢_{A′}^{∗} e, ϵ, ϵ

a zatem

w ∈ Z(A) ⟺ w ∈ Z(A′)

co zakończy dowód.

Pozostaje wi_{}ec dowieść (1)⇔ (2)

(1)⇒ (2) Przez indukcj_{}e ze wzgl_{}edu na długość obliczenia automatu A prowadz _{}acego od konfiguracji (q_{I}, w, Z_{I}) do (q, v, Z_{1} … Z_{m}), wykażemy że

e, w, Z′_{I} ⊢_{A′}^{∗} e, v, [q, Z_{1}, p_{1}][p_{1}, Z_{2}, p_{2}] … [p_{m−2}, Z_{m−1}, p_{m−1}][p_{m−1}, Z_{m}, p_{m}]

przy dowolnych p_{1}, …, p_{m}.

Dla obliczenia o długości 0

q_{I}, w, Z_{I} ⊢_{A}^{∗} q_{I}, w, Z_{I}

mamy, dla dowolnego p ∈ Q, obliczenie automatu A′ o długości 1, postaci

e, w, Z′_{I} ⊢_{A′} e, w, [q_{I}, Z_{I}, p]

Z kolei rozważmy obliczenie automatu A o długości > 0. Mamy zatem

q_{I}, w, Z_{I} ⊢_{A}^{∗} q′, av, Y_{1}Y_{2} … Y_{m}
⊢_{A} q, v, Z_{1} … Z_{k}Y_{2} … Y_{m}

dla pewnych a ∈ Σ ∪ {ϵ} oraz Y_{1}, …, Y_{m}, Z_{1}, …, Z_{k}, gdzie

q′, a, Y_{1} →_{A} q, Z_{1} … Z_{k}

jest przejściem automatu A.

Niech q_{1}, …, q_{k}, p_{2}, …, p_{m} ∈ Q, dowolne. Z założenia indukcyjnego, dla dowolnego p_{1}, mamy

(∗) e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, p_{1}][p_{1}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

Rozważymy teraz dwa przypadki, w zależności od tego czy k ≠ 0.

1. Gdy k > 0, mamy, z definicji A′, przejście

e, a, [q′, Y_{1}, q_{k}] →_{A′} e, [q, Z_{1}, q_{1}][q_{1}, Z_{2}, q_{2}] … [q_{k−1}, Z_{k}, q_{k}]

Nast_{}epnie, kład _{}ac w powyższej zależności (∗), p_{1} = q_{k}, mamy

e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, q_{k}][q_{k}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

St _{}ad,

e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, q_{k}][q_{k}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]
⊢_{A′} e, v, [q, Z_{1}, q_{1}][q_{1}, Z_{2}, q_{2}] … [q_{k−1}, Z_{k}, q_{k}][q_{k}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

2. Gdy k = 0, mamy, z definicji A′,

e, a, [q′, Y_{1}, q] →_{A′} e, ϵ

Kład _{}ac w zależności (∗), p_{1} = q, mamy

e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, q][q, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

St _{}ad

e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, q][q, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]
⊢_{A′} e, v, [q, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

co kończy dowód implikacji (1)⇒ (2).

(2)⇒ (1) Wykażemy implikacj_{}e silniejsz _{}a, a mianowicie, że z faktu iż

e, w, Z′_{I} ⊢_{A′}^{∗} e, v, [q, Z_{1}, p_{1}][p_{1}, Z_{2}, p_{2}] … [p_{m−2}, Z_{m−1}, p_{m−1}][p_{m−1}, Z_{m}, p_{m}]

dla pewnych p_{1}, …, p_{m}, wynika

q_{I}, w, Z_{I} ⊢_{A}^{∗} q, v, Z_{1} … Z_{m}

Podobnie jak poprzednio użyjemy indukcji ze wzgl_{}edu na długość obliczenia, ale tym razem chodzić b_{}edzie o obliczenie automatu A′ prowadz _{}ace od konfiguracji e, w, Z′_{I} do e, v, [q, Z_{1}, p_{1}][p_{1}, Z_{2}, p_{2}] … [p_{m−2}, Z_{m−1}, p_{m−1}][p_{m−1}, Z_{m}, p_{m}]. Zgodnie z definicj _{}a automatu A′, najkrótsze takie obliczenie ma oczywiście długość 1 i jest postaci

e, w, Z′_{I} ⊢_{A′} e, w, [q_{I}, Z_{I}, q]

Odpowiednie obliczenie automatu A jest obliczeniem trywialnym

q_{I}, w, Z_{I} ⊢_{A}^{∗}q_{I}, w, Z_{I}

Z kolei rozważmy możliwe obliczenie postaci

e, w, Z′_{I} ⊢_{A′}^{∗} e, av, [q′, Y_{1}, p_{1}][p_{1}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]
⊢_{A′} e, v, [q, Z_{1}, q_{1}][q_{1}, Z_{2}, q_{2}] … [q_{k−1}, Z_{k}, p_{1}][p_{1}, Y_{2}, p_{2}] … [p_{m−2}, Y_{m−1}, p_{m−1}][p_{m−1}, Y_{m}, p_{m}]

Ostatni krok tego obliczenia wykorzystuje przejście automatu A′,

e, a, [q′, Y_{1}, p_{1}] →_{A′} e, [q, Z_{1}, q_{1}][q_{1}, Z_{2}, q_{2}] … [q_{k−1}, Z_{k}, p_{1}]

gdzie

q′, a, Y_{1} →_{A} q, Z_{1} … Z_{k}

jest przejściem automatu A. (Poniższy argument działa zarówno dla k > 0 jak i dla k = 0, tzn. gdy ci _{}ag Z_{1} … Z_{k} jest pusty.)

Z założenia indukcyjnego, mamy

q_{I}, w, Z_{I} ⊢_{A}^{∗} q′, av, Y_{1} … Y_{m}

St _{}ad

q_{I}, w, Z_{I} ⊢_{A}^{∗} q′, av, Y_{1} … Y_{m}
⊢_{A} q, v, Z_{1} … Z_{k}Y_{2} … Y_{m}

Ta uwaga kończy dowód twierdzenia. □

2.2 Równoważność gramatyk bezkontekstowych i automatów ze stosem

Twierdzenie 2 Dla każdego automatu ze stosem A, można skonstruować gramatyk_{}e bezkontekstow _{}a G, tak _{}a że L(A) = L(G).

Dowód. Niech L = L(A). Na podstawie Faktu 1 i Twierdzenia 2.1, możemy znależć automat z jednym stanem, A′, taki że L = Z(A′), powiedzmy

A′ = (Σ, Γ, {e}, e, Z_{I}, δ, ∅)

Określamy gramatyk_{}e G w ten sposób, że

G = (Σ, Γ, Z_{I}, R)

gdzie zbiór reguł R jest zdefiniowany nast_{}epuj _{}aco:

Z →^{G} aY_{1} … Y_{m} ⇔ e, a, Z →_{A′} e, Y_{1} … Y_{m}

gdzie Z, Y_{1}, …, Y_{m} ∈ Γ, a ∈ Σ ∪ {ϵ}.

Pozostaje dowieść

Z(A′) = L(G)

“⊆” Udowodnimy nast_{}epuj _{}acy fakt.

(*) Przypuśćmy, że w = uv i e, w, Z_{I} ⊢_{A′}^{∗} e, v, γ. Wówczas Z_{I} →^{G∗} uγ.

Dowód przeprowadzimy przez indukcj_{}e ze wzgl_{}edu długość obliczenia cz_{}eściowego prowadz _{}acego od konfiguracji (e, w, Z_{I}) do (e, v, γ). Jeśli to jest obliczenie długości 0, to teza jest oczywista. Jeśli obliczenie jest dłuższe niż 0, to mamy

e, w, Z_{I} ⊢_{A′}^{∗} e, av, Y_{1} … Y_{m}
⊢_{A} e, v, Z_{1} … Z_{k}Y_{2} … Y_{m}

gdzie a ∈ Σ ∪ {ϵ}, u = u′a, dla pewnego u′, w = u′av i e, a, Y_{1} →_{A′} e, Z_{1} … Z_{k} jest przejściem automatu A′. Wówczas Y_{1} →^{G} aZ_{1} … Z_{k} jest reguł _{}a gramatyki G. Korzystaj _{}ac z założenia indukcyjnego mamy wi_{}ec

Z_{I} →^{G∗} u′Y_{1} … Y_{m} →^{G} u′aZ_{1} … Z_{k}Y_{2} … Y_{m}

co kończy dowód (*). Bior _{}ac pod uwag_{}e przypadek gdy v = γ = ϵ, otrzymujemy, że

e, w, Z_{I} ⊢_{A′}^{∗} e, ϵ, ϵ implikuje Z_{I} →^{G∗} w.

“⊇” Udowodnimy nast_{}epuj _{}acy fakt.

(**) Przypuśćmy, że w = uv ∈ Σ^{∗} i Z_{I} →^{l−G∗} uγ, γ ∈ Γ^{∗}. Wówczas e, w, Z_{I} ⊢_{A′}^{∗} e, v, γ.

Dowód przeprowadzimy przez indukcjȩ ze wzgl_{}edu na długość lewostronnego wyprowadzenia słowa uγ ze zmiennej Z_{I}. Kiedy wyprowadzenie ma długości 0, to u = ϵ, γ = Z_{I} i teza jest oczywista. Kiedy wyprowadzenie jest dłuższa niż 0, to mamy

Z_{I} →^{l−G∗} u′Y_{1} … Y_{m}
→^{l−G} u′aZ_{1} … Z_{k}Y_{2} … Y_{m}

gdzie, jak poprzednio, a ∈ Σ ∪ {ϵ}, u = u′a, w = u′av i Y_{1} →^{G} aZ_{1} … Z_{k} jest reguł _{}a gramatyki G, a zatem, zgodnie z definicj _{}a G, e, a, Y_{1} →_{A′} e, Z_{1} … Z_{k} jest przejściem automatu A′. Korzystaj _{}ac z założenia indukcyjnego mamy

e, w, Z_{I} ⊢_{A′}^{∗} e, av, Y_{1} … Y_{m}
⊢_{A′} e, v, Z_{1} … Z_{k}Y_{2} … Y_{m}

Przypuśćmy teraz, że Z_{I} →^{G∗} w. Na podstawie Twierdzenia 1 z Odcinka 3, istnieje wyprowadzenie lewostronne w z Z_{I}. Z (**) wynika, że wówczas e, w, Z_{I} ⊢_{A′}^{∗} e, ϵ, ϵ, czyli w ∈ Z(A′).

Ta uwaga kończy dowód twierdzenia. □

Twierdzenie 3 Dla każdej gramatyki bezkontekstowej G, można skonstruować automat ze stosem A, taki że L(G) = L(A).

Dowód. Niech G b_{}edzie gramatyk _{}a bezkontekstow _{}a. Jeśli L(G) = ∅, to zadanie jest trywialne, możemy wi_{}ec założyć, że L(G) ≠ ∅. Na podstawie Faktu 3 i Twierdzenia 2 z Odcinka 3, możemy skonstruować gramatyk_{}e w postaci normalnej Chomsky’ego, generuj _{}ac _{}a j_{}ezyk L(G) − {ϵ}. Zbudujemy automat A′, taki że Z(A′) = L(G′). Na podstawie Faktu 1, można dalej znaleźć automat, powiedzmy A′′, taki że L(A′′) = L(G′). Modyfikacja tego automatu w taki sposób by akceptował również słowo puste, o ile należy ono do L(G), jest łatw _{}a konstrukcj _{}a, któr _{}a pozostawiamy Czytelnikowi.

Niech

G′ = (Σ, V, X_{I}, R)

Określamy automat

A′ = (Σ, V, {e}, e, X_{I}, δ, ∅)

gdzie relacja przejść δ jest określona nast_{}epuj _{}aco:

• dla każdej reguły postaci X →^{G} Y Z,

e, ϵ, X →_{A′} e, Y Z

• dla każdej reguły postaci X →^{G} σ, σ ∈ Σ,

e, σ, X →_{A′} e, ϵ

Pozostaje dowieść

Z(A′) = L(G′)

Dowód tej równości opuszczamy, ponieważ jest analogiczny do dowodu podobnej równości w dowodzie Twierdzenia 2. Można powiedzieć wi_{}ecej: jeżeli do określonego przed chwil _{}a automatu zastosujemy konstrukcj_{}e z tamtego dowodu, to otrzymana gramatyka okaże si_{}e dokładnie (!) gramatyk _{}a G′. A zatem powyższa równość została już de facto udowodniona w dowodzie Twierdzenia 2. □

Wniosek 1 Nast_{}epuj _{}ace warunki s _{}a równoważne, dla j_{}ezyka L ⊆ Σ^{∗}.

1. L jest generowany przez gramatyk_{}e bezkontekstow _{}a,

2. L jest akceptowany przez niedeterministyczny automat ze stosem.

J_{}ezyki generowane przez gramatyki bezkontekstowe nazywamy j_{}ezykami bezkontekstowymi (ang. context-free languages). Gramatyki bezkontekstowe s _{}a metod _{}a syntezy j_{}ezyków bezkontekstowych. Poznaliśmy już także narz_{}edzie analizy tych j_{}ezyków: niedeterministyczny automat ze stosem. Udowodniliśmy, że obie metody: syntezy i analizy, dokładnie sobie odpowiadaj _{}a, tzn. automaty ze stosem rozpoznaj _{}a dokładnie te j_{}ezyki, które gramatyki syntezuj _{}a.

Klasa j_{}ezyków bezkontekstowych stanowi rozszerzenie klasy j_{}ezyków regularnych i obejmuje wiele naturalnych przykładów j_{}ezyków nie b_{}ed _{}acych regularnymi. Wiele elementów j_{}ezyków programowania, jak np. wyrażenia arytmetyczne, struktura bloków itp., da si_{}e opisać j_{}ezykami bezkontekstowymi. St _{}ad, ogromne znaczenie tych j_{}ezyków w konstrukcji kompilatorów.

3 Lematy o pompowaniu

W tym rozdziale poznamy dwa lematy o pompowaniu i ich zastosowanie do dowodzenia, że jakiś j_{}ezyk nie jest bezkontekstowy.

Lemat 1 (o pompowaniu) Niech L ⊆ Σ^{∗} b_{}edzie j_{}ezykiem bezkontekstowym. Wówczas istnieje stała M zależna tylko od L, taka, że dla każdego słowa α, jeśli α ∈ L i |α| ≥ M, to α można przedstawić α = α_{1}γ_{1}βγ_{2}α_{2} tak, że spełnione s _{}a nast_{}epuj _{}ace warunki:

• γ_{1}γ_{2} ≠ ϵ,

• |γ_{1}βγ_{2}| ≤ M,

• dla każdego i ≥ 0, α_{1}γ_{1}^{i}βγ_{2}^{i}α_{2} ∈ L.

Dowód. Niech G b_{}edzie gramatyk _{}a bezkontekstow _{}a w postaci Chomsky’ego generuj _{}ac _{}a j_{}ezyk L − {ϵ}, G = (Σ, V, X_{I}, R). Niech |V | = k, kładziemy

M = 2^{k}

Niech D b_{}edzie drzewem wyprowadzenia słowa α o długości |α| ≥ M. Wówczas gł_{}ebokość D jest ≥ k + 1. Istotnie, nietrudno wykazać przez indukcj_{}e, że maksymalne słowo, jakie można wygenerować przy pomocy drzewa o gł_{}ebokości i, ma długość 2^{i−1}. Niech p_{0}, p_{1}, p_{2}, …, p_{ℓ} b_{}edzie pewn _{}a ścieżk _{}a o maksymalnej długości w drzewie D. Mamy oczywiście ℓ ≥ k + 1, przy czym D(p_{ℓ}) ∈ Σ, natomiast, dla m < ℓ, D(m) ∈ V. Musz _{}a zatem istnieć dwa wierzchołki na tej ścieżce, w których pojawia si_{}e ta sama zmienna, powiedzmy D(p_{i}) = D(p_{j}) = X, i < j. Wybierzmy “pierwsz _{}a od końca” par_{}e o tej własności, tzn. załóżmy, że (∀m, n > i)m ≠ n ⇒ D(p_{m}) ≠ D(p_{n}). Oczywiście, podci _{}ag p_{i}, p_{i+1}, …, p_{ℓ−1} ma wówczas nie wi_{}ecej niż k+1 elementów. Rozważmy poddrzewo drzewa D wyznaczone przez wierzchołek p_{i}, które nazwiemy D′, formalnie (odc. 3, str. 3)

dom(D′) = {u : p_{i}u ∈ dom(D)}
D′(u) = D(p_{i}u) , dla u ∈ dom(D′)

Nietrudno sprawdzić, że D′ jest również drzewem wyprowadzenia, lecz tym razem ze zmiennej X = D(p_{i}). Zauważmy, że gł_{}ebokość tego drzewa jest ≤ k+1, co wynika z maksymalności ścieżki p_{1}, p_{2}, …, p_{ℓ} i uczynionej wyżej uwagi o mocy podci _{}agu p_{i}, p_{i+1}, …, p_{ℓ−1}. Niech γ b_{}edzie plonem drzewa D′, γ = y(D′). Na mocy zauważonej wcześniej zależności pomi_{}edzy gł_{}ebokości _{}a drzewa wyprowadzenia a długości _{}a generowanego słowa,

|γ| ≤ 2^{k} = M

Z kolei niech D′′ b_{}edzie poddrzewem D wyznaczonym przez wierzchołek p_{j}, analogicznie do D′. Zauważmy, że jest to również drzewo wyprowadzenia ze zmiennej X. Niech β = y(D′′).

Mamy wi_{}ec

γ = γ_{1}βγ_{2}

dla pewnych γ_{1}, γ_{2}.

Twierdzimy, że

γ_{1}γ_{2} ≠ ϵ

Istotnie, zgodnie z definicj _{}a gramatyki Chomsky’ego, wierzchołek p_{i} ma dwa nast_{}epniki w drzewie D, p_{i}1 i p_{i}2. Jednym z nich jest p_{i+1}, a drugi nie leży na wybranej przez nas ścieżce. Przypuśćmy, że p_{i+1} = p_{i}2. Niech D_{1} i D_{2} b_{}ed _{}a poddrzewami drzewa D wyznaczonymi przez wierzchołki p_{i}1 i p_{i}2 odpowiednio. Nietrudno zauważyć, że y(D_{1}) jest prefiksem słowa γ_{1}. Ponieważ, z definicji postaci gramatyki Chomsky’ego, y(D_{1}) ≠ ϵ, otrzymujemy γ_{1} ≠ ϵ. W przypadku, gdy wierzchołkiem leż _{}acym na ścieżce jest p_{i}1, argument przebiega podobnie.

Dla zakończenia dowodu pozostaje jeszcze wykazać, że spełniony jest ostatni warunek lematu o pompowaniu. Niech v ∈ {1, 2}^{∗} b_{}edzie tym słowem, że p_{j} = p_{i}v. (Intuicyjnie, v wyznacza ścieżk_{}e z wierzchołka p_{i} do wierzchołka p_{j}.) Określimy ci _{}ag drzew wyprowadzenia E_{0}, E_{1}, … i pomocniczo ci _{}ag słów u_{2}, u_{3}, … ∈ {1, 2}^{∗}, nast_{}epuj _{}aco:

• E_{0} jest rezultatem podstawienia w drzewie D drzewa D′′ na wierzchołek p_{i}, w notacji symbolicznej (por. Odc. 3, str. 4), E_{0} = D[p_{i} ← D′′].

• E_{1} = D.

• E_{2} jest rezultatem podstawienia w drzewie D drzewa D′ na wierzchołek p_{j}, tj. E_{2} = D[p_{j} ← D′], i u_{2} = p_{j}v.

• E_{3} jest rezultatem podstawienia w drzewie E_{2} drzewa D′ na wierzchołek u_{2}, tj. E_{3} = E_{2}[u_{2} ← D′], i u_{3} = u_{2}v.

• Ogólniej, dla n ≥ 2, E_{n+1} jest rezultatem podstawienia w drzewie E_{n} drzewa D′ na wierzchołek u_{n}, tj. E_{n+1} = E_{n}[u_{n} ← D′], i u_{n+1} = u_{n}v.

Niech α_{1}, α_{2} b_{}ed _{}a tymi słowami, że γ = α_{1}βα_{2}. Opieraj _{}ac si_{}e wprost na powyższych definicjach, nietrudno wykazać, że

\begin{aligned}y(E_{0}) & = & α_{1}βα_{2} \\ y(E_{1}) & = & α_{1}γ_{1}βγ_{2}α_{2} \\ y(E_{2}) & = & α_{1}γ_{1}γ_{1}βγ_{2}γ_{2}α_{2} \\ y(E_{3}) & = & α_{1}γ_{1}γ_{1}γ_{1}βγ_{2}γ_{2}γ_{2}α_{2} \\ … & … & … \\ y(E_{n}) & = & α_{1}γ_{1}^{n}βγ_{2}^{n}α_{2} \end{aligned}

□

Przyk”lad 1 Zbiór {a^{n}b^{n}a^{n} : n ∈ N} nie jest bezkontekstowy. Istotnie, niech M b_{}edzie stał _{}a z lematu i niech n > M. Przypuśćmy, że a^{n}b^{n}a^{n} = α_{1}γ_{1}βγ_{2}α_{2} jest dekompozycj _{}a z lematu. Nietrudno zauważyć, że γ_{1}, γ_{2} ∈ {a}^{∗} ∪ {b}^{∗}. Analizuj _{}ac poszczególne przypadki, łatwo dochodzimy do sprzeczności. Na przykład, gdy γ_{1} ∈ {a}^{∗} i γ_{2} ∈ {b}^{∗}, to również słowo a^{n+|γ_{1}|}b^{n+|γ_{2}|}a^{n} powinno należeć do j_{}ezyka, wbrew definicji.

Jeśli w ∈ Σ^{∗} i |w| = m, to elementy zbioru {1, …, m} b_{}edziemy nazywali pozycjami w słowie w. W kolejnym lemacie b_{}edziemy rozważali słowa z wyróżnionymi pozycjami, tj., formalnie, pary (w, P), gdzie P ⊆ {1, …, |w|}.

Lemat 2 (lemat Ogdena) Niech L ⊆ Σ^{∗} b_{}edzie j_{}ezykiem bezkontekstowym. Wówczas istnieje stała M zależna tylko od L, taka, że dla każdego słowa α ∈ L z dowolnie wyróżnionymi co najmniej M pozycjami, α można przedstawić α = α_{1}γ_{1}βγ_{2}α_{2} tak, że spełnione s _{}a nast_{}epuj _{}ace warunki:

• γ_{1} i γ_{2} zawieraj _{}a wspólnie co najmniej jedn _{}a wyróżnion _{}a pozycj_{}e,

• słowo γ_{1}βγ_{2} zawiera nie wi_{}ecej niż M wyróżnionych pozycji,

• dla każdego i ≥ 0, α_{1}γ_{1}^{i}βγ_{2}^{i}α_{2} ∈ L.

Dowód (szkic). Argument jest podobny jak w dowodzie lematu o pompowaniu. Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a bezkontekstow _{}a w postaci Chomsky’ego generuj _{}ac _{}a j_{}ezyk L − {ϵ} i niech |V | = k. Kładziemy

M = 2^{k+1}

Przypuśćmy, że D jest drzewem wyprowadzenia słowa α, w którym wyróżnione jest ≥ M pozycji (oczywiście wówczas także |α| ≥ M). Strategia wyboru ścieżki p_{0}, p_{1}, …, p_{ℓ} jest nast_{}epuj _{}aca. Oczywiście, p_{0} = ϵ. Z kolei przypuśćmy, że już wybraliśmy do naszej ścieżki wierzchołki p_{0}, p_{1}, …, p_{m}, 0 ≤ m < ℓ. Wierzchołek p_{m} ma w drzewie D dwa nast_{}epniki: p_{m}1 i p_{m}2, które wyznaczaj _{}a dwa poddrzewa drzewa D, powiedzmy, D_{1} i D_{2} odpowiednio. Wybieramy ten nast_{}epnik, w którego poddrzewie znajduje si_{}e wi_{}ecej wyróżnionych pozycji, a w przypadku remisu wybieramy, powiedzmy, p_{m}1. Nietrudno zauważyć, że tak określona ścieżka p_{0}, p_{1}, …, p_{ℓ} prowadzi do liścia odpowiadaj _{}acego jakiejś wyróżnionej pozycji w generowanym słowie α.

Każdy wierzchołek p_{m} na ścieżce o tej własności, że oba poddrzewa wyznaczone przez nast_{}epniki p_{m} zawieraj _{}a jakieś wyróżnione pozycje, nazwiemy punktem rozgał_{}ezienia. Zauważmy, że jeżeli p_{m} jest punktem rozgał_{}ezienia, to poddrzewo wyznaczone przez p_{m+1} zawiera istotnie mniej ale co najmniej połow_{}e pozycji, jakie znajdowały si_{}e w drzewie wyznaczonym przez p_{m}. Pami_{}etaj _{}ac o tym, że w drzewie wyznaczonym przez p_{0} (tj. drzewie D) jest ≥ 2^{k+1} wyróżnionych pozycji, nietrudno wykazać, że na ścieżce p_{0}, p_{1}, …, p_{ℓ} musi leżeć co najmniej k +1 punktów rozgał_{}ezienia. Wśród tych punktów możemy wi_{}ec znaleźć dwa takie, powiedzmy p_{i}, p_{j}, że i < j i D(p_{i}) = D(p_{j}). Dalej dowód przebiega bardzo podobnie jak w przypadku lematu o pompowaniu. Mianowicie, wybieramy “pierwsz _{}a od końca” par_{}e p_{i}, p_{j} o powyższej własności i słowa α_{1}, γ_{1}, β, γ_{2}, α_{2} określamy analogicznie, jak w tamtym dowodzie.

Aby wykazać, że słowo α_{1}βα_{2} zawiera nie wi_{}ecej niż M wyróżnionych pozycji, wystarczy zauważyć, że p_{i} jest co najwyżej “k + 1-szym od końca” punktem rozgał_{}ezienia na ścieżce, oraz, że, ogólnie, poddrzewo wyznaczone przez “m-ty od końca” punkt rozgał_{}ezienia na naszej ścieżce, zawiera co najwyżej 2^{m} pozycji. Fakt, że jedno ze słów γ_{1}, γ_{2} zawiera co najmniej jedn _{}a wyróżnion _{}a pozycj_{}e, wynika z tego, że p_{i} jest punktem rozgał_{}ezienia. Ostatni warunek lematu jest otrzymany analogicznie, jak w przypadku dowodu lematu o pompowaniu. □

Przyk”lad 2 J_{}ezyk

L = {a^{i}b^{j}c^{k} : i ≠ j, j ≠ k, i ≠ k}

nie jest bezkontekstowy. Istotnie, niech n b_{}edzie stał _{}a z lematu Ogdena. Rozważmy słowo α = a^{n}b^{n+n!}c^{n+2·n!}, w którym s _{}a wyróżnione wszystkie pozycje a i tylko te. Przypuśćmy, że α = α_{1}γ_{1}βγ_{2}α_{2} jest dekompozycj _{}a z lematu. Wówczas przynajmniej jedno ze słów γ_{1}, γ_{2} musi zawierać przynajmniej jedno a. Nietrudno widzieć, że musi zachodzić γ_{1} ∈ {a}{a}^{∗} oraz γ_{2} ∈ {a}^{∗} ∪ {b}^{∗} ∪ {c}^{∗}. W każdym przypadku możemy łatwo dojść do sprzeczności. Przypuśćmy na przyład, że γ_{2} ∈ {b}^{∗}. Niech p = |γ_{1}|, q = |γ_{2}|. Mamy 1 ≤ p ≠ n, niech wi_{}ec p_{1} = n!/p. Wówczas, z trzeciego punktu lematu Ogdena, również słowo

a^{n+p·(2p_{1})}b^{n+p·(2 p_{1})}c^{n+2·n!}

powinno należeć do L, ale n + p · (2p_{1}) = n + 2 · n!, co przeczy definicji L. □

4 Własności domkni_{}ecia

W tym punkcie rozważymy własności domkni_{}ecia, tzn. na jakie operacje jest, a na jakie nie jest zamkni_{}eta klasa j_{}ezyków bezkontekstowych. Dowody poniższych faktów pozostawiamy jako ćwiczenia.

Fakt 2 Rodzina j_{}ezyków bezkontekstowych jest zamkni_{}eta na operacje skończonej sumy, konkatenacji i iteracji (“gwiazdki”).

Uwaga. Rodzina j_{}ezyków bezkontekstowych nie jest natomiast zamkni_{}eta na operacje przeci_{}ecia i uzupełnienia. Istotnie, niech

M = {a^{n}b^{n}a^{n} : n ∈ N}

b_{}edzie j_{}ezykiem, o którym wykazaliśmy, że nie jest bezkontekstowy (Przykład 1). Nietrudno pokazać, że

M = {a^{n}b^{n} : n ∈ N}a^{∗} ∩ a^{∗}{b^{n}a^{n} : n ∈ N}
M = {a, b}^{∗} − {a^{i}b^{j}a^{k} : i ≠ j lub j ≠ k}

gdzie j_{}ezyki wyst_{}epuj _{}ace po prawych stronach równości s _{}a bezkontekstowe.

Fakt 3 Rodzina j_{}ezyków bezkontekstowych jest zamkni_{}eta na przeci_{}ecia z j_{}ezykami regularnymi, tzn. jeśli j_{}ezyk L jest bezkontekstowy a j_{}ezyk R jest regularny, to j_{}ezyk L ∩ R jest bezkontekstowy.

Fakt 4 Rodzina j_{}ezyków bezkontekstowych jest zamkni_{}eta na ilorazy przez j_{}ezyki regularne, tzn. jeśli j_{}ezyk L jest bezkontekstowy a j_{}ezyk R jest regularny, to j_{}ezyki LR^{−1} i R^{−1}L s _{}a bezkontekstowe.

Fakt 5 Rodzina j_{}ezyków bezkontekstowych jest zamkni_{}eta na podstawienia, tzn. jeśli j_{}ezyk L jest bezkontekstowy i f : Σ → P (Γ^{∗}) jest funkcj _{}a tak _{}a, że, dla każdego σ ∈ Σ, f(σ) jest j_{}ezykiem bezkontekstowym, to f̂(L) jest j_{}ezykiem bezkontekstowym.

Fakt 6 Rodzina j_{}ezyków bezkontekstowych jest zamkni_{}eta na przeciwobrazy homomorficzne, tzn. jeśli f : Σ → Γ^{∗} jest homomorfizmem i M ⊆ Γ^{∗} jest bezkontekstowy, to j_{}ezyk

f̂^{−1}(M) = {w ∈ Σ^{∗} : f̂(w) ⊆ M}

jest bezkontekstowy.

Ćwiczenia

1. (*) Dowieść, że każdy j_{}ezyk bezkontekstowy nad jednoliterowym alfabetem jest regularny.

2. Czy przy pomocy automatu skończonego można rozpoznać, ze w słowie nad alfabetem {a, b, c} jedna z liter wyst_{}epuje co najmniej tyle samo razy co dwie pozostałe? Czy można rozpoznać t_{}e własność przy pomocy automatu ze stosem?

3. Dowieść, że j_{}ezyk {ww : w ∈ Σ^{∗}} nie jest bezkontekstowy, o ile |Σ| ≥ 2.

4. Niech L b_{}edzie j_{}ezykiem regularnym. Które z nast_{}epuj _{}acych j_{}ezyków s _{}a regularne

lub bezkontekstowe?

• {ww : w ∈ L}

• {ww^{R} : w ∈ L}

• {wv^{R} : w, v ∈ L}

5. Dowieść, że j_{}ezyk {a^{i}b^{j}c^{k} : i ≠ j, j ≠ k} nie jest bezkontekstowy.

6. Dowieść, że j_{}ezyk {w$v : v jest podsłowem w} nie jest bezkontekstowy, natomiast j_{}ezyk {w$v^{R} : v jest podsłowem w}, jest bezkontekstowy.

7. Czy nast_{}epujacy zbiór jest j_{}ezykiem bezkontekstowym:

Zbior słów p$w, gdzie p jest wyrażeniem regularnym nad alfabetem {a, b}, a w jest słowem należ _{}acym do j_{}ezyka wyznaczonego przez p.

Analogiczne pytanie dla p$w^{R}.

8. Niech A – alfabet, A′ = {a′ : a ∈ A}. Określamy homomorfizmy h, h_{1}, h_{2} z A ∪ A′ w A nast_{}epuj _{}aco: h(a) = h(a′) = a, h_{1}(a) = a, h_{1}(a′) = ϵ, h_{2}(a) = ϵ, h_{2}(a′) = a. Definiujemy przeplot j_{}ezyków L_{1} i L_{2}:

Shuffle(L_{1}, L_{2}) = {x : (∃y ∈ h^{−1}(x))h_{1}(y) ∈ L_{1} ∧ h_{2}(y) ∈ L_{2}}

Dowieść, że

(a) przeplot dwóch jezyków regularnych jest regularny,

(b) przeplot j_{}ezyka bezkontekstowego z regularnym jest bezkontekstowy,

(c) przeplot dwóch jezykow bezkontekstowych nie musi być bezkontekstowy (wskazówka: {a^{n}b^{m}c^{n}d^{m} : n, m ∈ N} nie jest bezkontekstowy)