Obsah

N-AP14

Zadání

Bezkontextové jazyky. Bezkontextové gramatiky. Zásobníkové automaty. Normální formy bezkontextových gramatik. Převod bezkontextové gramatiky na zásobníkové automaty. Použití pumping lemmatu a uzávěrových vlastností bezkontextových jazyků.

Bezkontextové jazyky

Jazyk L je bezkontextový, pokud existuje bezkontextová gramatika G taková, že L(G)=L.1)

Definice

Bezkontextová gramatika (CFG) G je čtveřice (N, \Sigma, P, S), kde:
  • N je neprázdná konečná množina neterminálních symbolů
  • \Sigma je konečná množina terminálních symbolů taková, že N \cap \Sigma = \emptyset
  • P \subseteq N \times V^\ast je konečná množina pravidel (V = N \cup \Sigma)
  • S \in N je počáteční neterminál

Současně třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků. Tj. jazyk L je bezkontextový, pokud je akceptován nějakým zásobníkovým automatem (existuje zásobníkový automat M, takový, že L(M)=L).

Způsoby reprezentace bezkontextových jazyků

Bezkontextové jazyky lze reprezentovat:

Zásobníkový automat

Na vstupní pásce je napsáno slovo (nad jistou vstupní abecedou) – lze z ní pouze číst, čtecí hlava se pohybuje pouze vpravo. Automat může na vrchol zásobníku ukládat symboly (z jisté abecedy) a ty následně číst – čte vždy jen vrchol zásobníku, přečtený symbol je odstraněn = systém LIFO (Last In First Out).

Definice 3.36. - PDA 2)

Nedeterministický zásobníkový automat (PushDown Automaton, PDA) je sedmice M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F), kde
Q je konečná množina, jejíž prvky nazýváme stavy,
\Sigma je konečná množina, tzv. vstupní abeceda,
\Gamma je konečná množina, tzv. zásobníková abeceda,
\delta : (Q \times (\Sigma \cup{{\varepsilon}})\times \Gamma) \rightarrow P_{Fin}(Q \times \Gamma^{*}), tzv. (parciální) přechodová funkce (zápis P_{Fin}(Q \times \Gamma^{*}) značí množinu všech konečných podmnožin množiny Q\times \Gamma^{*} – dvojice stav a řetězec symbolů zásobníkové abecedy),
q_{0} \in Q je počáteční stav,
Z_{0} \in \Gamma je počáteční symbol v zásobníku,
F \subseteq Q je množina koncových stavů.

\delta(q_{0}, a, Z_{0}) = \{(q_{0}, AZ_{0})\}; Z_{0} … dno zásobníku, A … vrchol zásobníku, přidal se v tomto kroku
\delta(q_{0}, c,  A) = \{(q_{1}, A)\} … obsah zásobníku se nezměnil, pouze se přešlo do stavu q1 \delta(q_{1}, b, A) = \{(q_{1}, \varepsilon)\} … stav se nezměnil, ze zásobníku se přečetlo A – bylo odebráno
vrchol zásobníku běžného PDA se píše vlevo

Rozdíl mezi zásobníkovým automatem a rozšířeným zásobníkovým automatem je následující: Zásobníkový automat má přechodovou funkci \delta definovanou jako zobrazení z Q \times (\Sigma \cup \{ \epsilon \}) \times \Gamma do konečných podmnožin množiny (Q\times \Gamma^\ast). Oproti tomu rozšířený zásobníkový automat má definovanou rozšířenou přechodovou funkci \delta jako zobrazení z konečné podmnožiny množiny Q \times (\Sigma \cup \{ \epsilon \}) \times \Gamma^\ast do konečných podmnožin množiny (Q\times \Gamma^\ast ).

Neformálně řečeno, rozšířený zásobníkový automat „vidí“ hlouběji do zásobníku – tj. čte 0–n vrchních symbolů.

Výpočet zásobníkového automatu

Definice 3.37. Konfigurace, krok výpočtu 3)

Nechť M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F) je PDA.
Konfigurací nazveme libovolný prvek (p, w, \alpha) \in Q \times \Sigma^{*} \times \Gamma^{*}.
Na množině všech konfigurací automatu M definujeme binární relaci krok výpočtu |\frac{\ \ \ }{\ M \ } takto:
(p, aw, Z \alpha) |\frac{\ \ \ }{\ M \ }(q, w, \gamma \alpha) \Leftrightarrow^{def} \exists(q, \gamma) \in  \delta (p, a, Z) pro a \in \Sigma \cup \lbrace \varepsilon \rbrace

Reflexivní a tranzitivní uzávěr relace |\frac{\ \ \ }{\ M \ } značíme |\frac{\ * \ }{\ M \ }.
Je-li M zřejmý z kontextu, píšeme pouze |\frac{\ \ \ }{\ \ \ } resp. |\frac{\ * \ }{\ \ \ }.

Akceptující výpočet PDA

Definice 3.37. (pokračování) - akceptování 4)

Jazyk akceptovaný PDA M koncovým stavem definujeme jako
L(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q_{f}, \varepsilon, \alpha), kde q_{f} \in  F, \alpha \in \Gamma^{*} \rbrace

a jazyk akceptovaný PDA M prázdným zásobníkem definujeme
L_{e}(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q, \varepsilon, \varepsilon), kde q \in Q \rbrace.

Takto definovaný PDA je nedeterministický – akceptuje slovo, jestliže existuje alespoň jeden výpočet, který vede z počáteční konfigurace do akceptující. V případě možnosti automat „hádá správně“.

Ekvivalence dvou způsobů akceptování

Pro každý jazyk L platí:

Věta 3.39, 5)

L = L(N) pro nějaký PDA N \Leftrightarrow  L = L_{e}(M) pro nějaký PDA M.

PDA N akceptuje koncovým stavem, PDA M prázdným zásobníkem

koncový stav => prázdná paměť

Intuice: K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
• pokračovat v simulaci automatu N nebo
• přejít do nově přidaného stavu q_{\varepsilon}, v němž vyprázdní zásobník.
Komplikace: Automat N by vyprázdnil zásobník, aniž by došel do koncového stavu – akceptoval by i nežádoucí vstup.
Řešení: Před zahájením simulace bude u M na dně zásovníku nový symbol, který nedovolíme odstranit jinde, než ve stavu q_{\varepsilon}.

prázdná paměť => koncový stav

K danému M zkonstruujeme N simulující jeho činnost.
• N si před simulací přidá na dno zásobníku nový symbol.
• Je-li N schopen číst tento symbol (tj. zásobník automatu M je prázdný), potom N přejde do nově přidaného stavu q_{f}, který je koncovým stavem.

důkaz viz skripta 6), konstrukce viz slidy 7)

Grafická reprezentace konfigurací

Příklad: PDA A = (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \{r\}) - akceptuje koncovým stavem
PDA A'= (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \emptyset) - akceptuje prázdným zásobníkem

Přechodovou funkci mají oba automaty stejnou:
\delta(q, a, Z) = \{(q, AZ)\} \delta(q, a, A) = \{(q, AA)\} \delta(q, c, Z) = \{(r, Z)\} \delta(q, c, A) = \{(r, A)\} \delta(r, b, Z) = \{(r, \epsilon)\} \delta(r, b, A) = \{(r, \epsilon)\}

Grafické znázornění obou automatů, žlutě vybarvené jsou konfigurace, ve kterých akceptuje automat A, v tlustě orámované konfiguraci akceptuje automat A'

Normální formy bezkontextových gramatik

Chomského normální forma

Definice 3.19

Bezkontextová gramatika G = (N, \Sigma, P, S) je v Chomského normální formě (CNF) \Leftrightarrow\ G je bez \epsilon-pravidel (dle def. 3.13) a každé pravidlo z P má jeden z těchto tvarů:
  1. A \rightarrow BC,\ B,C\in N
  2. A \rightarrow a,\ a \in \Sigma

Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Chomského normální formě. Algoritmus transformace do CNF lze nalézt ve skriptech Automaty a gramatiky, strana 67. Ve zkratce algoritmus funguje tak, že pravé strany délky větší než 2 nahradí novými neterminály, a tak se tato pravá strana zkrátí. Například pravidlo X → ABC se změní na pravidla X → A<BC>, <BC> → BC (<BC> je nový neterminál). Pro pravé strany délky 2, které se skládají z terminálu a neterminálu nahradí terminál novým neterminálem. Např. X → aC se změní na X → <a>C, <a> → a.

Greibachové normální forma

Definice 3.33

Bezkontextová gramatika G = (N, \Sigma, P, S) je v Greibachové normální formě (GNF) právě když:
  • G je bez \epsilon-pravidel (dle def. 3.13)
  • každé pravidlo z P je tvaru A \rightarrow a\alpha, kde a \in \Sigma a \alpha \in N^\ast

Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou v Greibachové normální formě. Velmi zhruba naznačený postup je následující: Pokud je L(G) prázdný, pak jej definujeme jako jediné pravidlo (S\rightarrow aS). Pokud je L(G) neprázdný, odstraníme levou rekurzi a převedeme do GNF. Algoritmus transformace do GNF lze nalézt ve skriptech Automaty a gramatiky, strana 73,74.

Převod bezkontextové gramatiky na zásobníkové automaty

Věta 3.51 8)

Ke každému PDA M lze sestrojit CFG G takovou, že L_{e}(M) = L(G).

Jednoduchý algoritmus na prvnim slidu http://www.nvc.cs.vt.edu/~jzhang/cs5104/Note-8.pdf priklad si bud vygooglovat nebo strana 89 ve skriptech FJA

Věta 3.47 9)

Ke každé CFG G lze sestrojit PDA M takový, že L(G) = L_{e}(M).

Strana 25, 26 http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/PDA.pdf

Důsledek 3.52 10)

Třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.

Konstrukce PDA řeší problém syntaktické analýzy. (platí pro dané G a w: w \in L(G)?)
w \in L(G) \Leftrightarrow v G existuje derivační strom s výsledkem w.

Nedeterministická syntaktická analýza shora dolů

Budování derivačního stromu simuluje levé derivace, tj. vždy rozvíjíme nejlevější neterminál.

Důsledek 3.47 11)

Ke každé CFG G lze sestrojit PDA M takový, že L(G) = L_{e}(M).

Důkaz. K dané gramatice G konstruujeme PDA M, který simuluje levé derivace v G (rozvíjíme nejlevější neterminál).

M = (\lbrace q \rbrace, \Sigma,N \cup \Sigma, \delta, q, S, \emptyset), kde \delta je definována:

korektnost + důkaz viz skripta 12)

Nedeterministická syntaktická analýza zdola nahoru

Lemma 3.55 13)

Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R takový, že L(G) = L(R).

Důkaz. Vrchol zásobníku píšeme vpravo. Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G v obráceném pořadí.
PDA R má kroky dvojího typu:

  1. může kdykoli číst do zásobníku vstupní symbol,
  2. (redukce) je-li na vrcholu zásobníku řetěz tvořící pravou stranu nějakého pravidla v G, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte).

Nechť G = (N, \Sigma, P, S).
Položme R = (\lbrace q, r \rbrace, \Sigma, N \cup \Sigma \cup \lbrace \bot \rbrace, \delta, q, \bot, \lbrace r \rbrace ), kde \bot je nově přidaný symbol a kde \delta je definována takto:

  1. \delta(q, a, \varepsilon) = \lbrace(q, a)\rbrace pro všechna a \in \Sigma …načítání vstupu na zásobník,
  2. je-li A \rightarrow \alpha, pak \delta(q, \varepsilon, \alpha) obsahuje (q, A) …redukce,
  3. \delta(q, \varepsilon, \bot S) = \lbrace(r, \varepsilon)\rbrace …akceptování.

korektnost viz slajdy 14)

Příklad:

Zadání:
G = ({S, A, B}, {a, b}, P, S)
P =
{S → \varepsilon | abSA
A → AaB | aB | a,
B → aSS | bA | \varepsilon}
Derivační strom pro slovo w = abababaa
Automat, který provádí syntaktickou analýzu shora dolů: A = ({q}, {a,b}, {S, A, B, a, b}, \delta, q, S, \emptyset)
2 typy přechodových fcí:

\delta(q, \varepsilon, S) = {(q, \varepsilon), (q, abSA)}
\delta(q, \varepsilon, A) = {(q, AaB), (q, aB), (q, a)}
\delta(q, \varepsilon, B) = { (q, aSS), (q, bA), (q, \varepsilon)}

\delta(q, a, a) = {(q, \varepsilon)}
\delta(q, b, b) = {(q, \varepsilon)}

(intuice: postupuju podle derivačního stromu, sleduju jeho rozvíjení odshora a čtu ho zleva)
vrchol zásobníku je vlevo (q, abababaa, S) |\frac{\ \ \ }{\ \ \ } (q, abababaa, abSA) |\frac{\ \ \ }{\ \ \ } (q, bababaa, bSA) |\frac{\ \ \ }{\ \ \ }
(q, ababaa, SA) |\frac{\ \ \ }{\ \ \ } (q, ababaa, A) |\frac{\ \ \ }{\ \ \ } (q, ababaa, AaB) |\frac{\ \ \ }{\ \ \ }
(q, ababaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, BaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, bAaB) |\frac{\ \ \ }{\ \ \ }
(q, abaa, AaB) |\frac{\ \ \ }{\ \ \ } (q, abaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, baa, BaB) |\frac{\ \ \ }{\ \ \ }
(q, baa, bAaB) |\frac{\ \ \ }{\ \ \ } (q, aa, AaB) |\frac{\ \ \ }{\ \ \ } (q, aa, aaB) |\frac{\ \ \ }{\ \ \ }
(q, a, aB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, B) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \varepsilon) … celé slovo se přečetlo a zásobník se vyprázdnil \rightarrow automat slovo akceptuje

Automat pro syntaktickou analýzu zdola nahoru: A_{2} = (\{q, r\}, \{ a,b\} , \{S, A, B, a, b, \bot\}, \delta, q, \bot, \{ r\}) 3 typy přechodových funkcí:

\delta(q, a, \varepsilon) = {(q, a)}
\delta(q, b, \varepsilon) = {(q, b)}

\delta(q, \varepsilon, abSA) = {(q, S)}
\delta(q, \varepsilon, \varepsilon) = {(q, S), (q, B)} ! ! ! Nesmí být rozděleno na: \delta(q, \varepsilon, \varepsilon) = {(q, S)} a \delta(q, \varepsilon, \varepsilon) = {(q, B)}, nebyla by to pak funkce.
\delta(q, \varepsilon, AaB) = \delta(q, \varepsilon, aB) = \delta(q, \varepsilon, a) = {(q, A)}
\delta(q, \varepsilon, aSS) = \delta(q, \varepsilon, bA) = {(q, B)}

\delta(q, \varepsilon, \botS) = {(r, \varepsilon)}

(Intuice: čtu derivační strom zleva – jako když teče voda (= používám první skupinu pravidel), pokud by voda musela téct do kopce, použiju pravidlo z druhé skupiny)
vrchol zásobníku je vpravo (q, abababaa, \bot) |\frac{\ \ \ }{\ \ \ } (q, bababaa, \bot a) |\frac{\ \ \ }{\ \ \ } (q, ababaa, \bot ab) |\frac{\ \ \ }{\ \ \ }
(q, ababaa, \bot abS) |\frac{\ \ \ }{\ \ \ } (q, babaa, \bot abSa) |\frac{\ \ \ }{\ \ \ } (q, abaa, \bot abSab) |\frac{\ \ \ }{\ \ \ }
(q, baa, \bot abSaba) |\frac{\ \ \ }{\ \ \ } (q, aa, \bot abSabab) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSababa) |\frac{\ \ \ }{\ \ \ }
(q, a, \bot abSababA) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabA) |\frac{\ \ \ }{\ \ \ }
(q, a, \bot abSaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSAa) |\frac{\ \ \ }{\ \ \ }
(q, \varepsilon, \bot abSAaB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot S) |\frac{\ \ \ }{\ \ \ } (r, \varepsilon, \varepsilon) … automat přečetl celé slovo a přešel do koncového stavu r, slovo akceptuje.

U nedeterministické analýzy automat slovo neakceptuje, pokud žádný z možných výpočtů není akceptující.

Použití pumping lemmatu a uzávěrových vlastností bezkontextových jazyků

Použití lemmatu o vkládání pro bezkontextové jazyky

Věta 3.24

Nechť L je CFL. Pak existují přirozená čísla p,q (závisející na L) taková, že každé slovo z\in L, délky alespoň p, lze psát ve tvaru z=uvwxy, kde alespoň jedno ze slov v,x je neprázdné (tj. vx \neq \epsilon ), |vwx| \le q a uv^i wx^iy \in L pro všechna i \ge 0.

Explicitněji lze lemma přepsat takto:
Za předpokladu, že L \in CFL, pak
\exists p,q \in N.

\forall z\in L.\ |z|>p.

\exists u,v,w,x,y \in \Sigma*.\ z=uvwxy\ \wedge vx\neq \epsilon\ \wedge|vwx| \leq q.

\forall i\geq 0 :\ uv^iwx^iy\in L

Lemma o vkládání je ve tvaru implikace P ⇒ Q, kde P je výrok, že L je CFL a Q jsou uvedené vlastnosti. Této implikace (resp. její kontrapositivní formu) lze použít k důkazu, že nějaký jazyk není CFL. Stačí ukázat platnost následujícího tvrzení:

Pro libovolnou konstantu n existuje slovo z, |z|>n takové, že pro všechna slova u, v, w, x, y splňující: z = uvwxy, vx \neq \epsilon a |vwx| \le n existuje takové i, že uv^i wx^i y \notin L.

Příklad

L=\{ wcw \, \mid\, w \in \{a,b \}*\}

Pro libovolnou konstantu n existuje slovo z \in L , |z| > n: Zvolíme slovo z jako libovolné, pro důkaz vhodné, slovo z z jazyka L - z = a^n b^n c a^n b^n. Dále pro každé libovolné rozdělení slova z splňující následující podmínky: z = uvwxy,\ vx \neq \epsilon,\ |vwx| \le n musí existovat i \in N_0 takové, že uv^i wx^iy \notin L.

Nyní musíme takové i nalézt. Položme tedy i=0 a ověříme, že uwy \notin L rozebráním jednotlivých případů:

  1. c není podslovo vwx. Potom ale uwy = z' ca^n b^n nebo uwy = a^n b^n c z', kde |z'| < 2n. Z toho plyne, že uwy \notin L.
  2. c je podslovo vwx. Tuto situaci rozdělíme ještě na další dva případy:
    • c je podslovo vx: Pak ale c \notin uwy, z čehož plyne, že uwy \notin L
    • c je podslovo w: |vwx| \leq n,\ uwy = a^n b^{n-|v|} c a^{n-|x|} b^n. Současně vx \neq \epsilon a tudíž |v|+|x| > 0 a tedy uwy \notin L.

Uzávěrové vlastnosti bezkontextových jazyků

Třída bezkontextových jazyků je uzavřena vzhledem k operacím:

Třída bezkontextových jazyků není uzavřena vzhledem k operacím:

Pro následující případy uvažujme:
L_1 je generován CFG G_1 = (N_1,\Sigma_1, P_1, S_1), L_2 je generován CFG G_2 = (N_2,\Sigma_2, P_2, S_2) a bez újmy na obecnosti budeme předpokládat N_1 \cap N_2 = \emptyset.

Sjednocení

Definujme G = (N_1 \cup N_2 \cup \{S\},\,\Sigma_1 \cup \Sigma_2,\, P,\, S), kde S je nový symbol a P = P_1 \cup P_2 \cup \{ S\rightarrow S_1,\, S\rightarrow S_2\}

Jazyk L = L_1 \cup L_2 je generován gramatikou G.

Zřetězení

Definujme G = (N_1 \cup N_2 \cup \{S\},\,\Sigma_1 \cup \Sigma_2,\, P,\, S), kde S je nový symbol a P = P_1 \cup P_2 \cup \{ S\rightarrow S_1S_2\}

Jazyk L = L_1 . L_2 je generován gramatikou G.

Iterace a pozitivní iterace

Definujme G = (N_1 \cup \{S\},\,\Sigma_1,\, P,\, S), kde S je nový symbol a P = P_1 \cup \{ S\rightarrow SS_1|\epsilon \}

Jazyk L = L_1^{\ast} je generován gramatikou G.

Definujme G = (N_1 \cup \{S\},\,\Sigma_1,\, P,\, S), kde S je nový symbol a P = P_1 \cup \{ S\rightarrow SS_1|S_1 \}

Jazyk L = L_1^{+} je generován gramatikou G.

Průnik a doplněk

L_1 = \{ a^n b^n c^m\, \mid\, m,n \ge 1\},\ L_2 = \{ a^m b^n c^m\, \mid\, m,n \ge 1\}

Kdyby byla třída bezkontextových jazyků uzavřena vzhledem k operaci průnik, pak i L_1 \cap L_2 = \{ a^n b^n c^n \, \mid \, n \ge 1 \} by musel být bezkontextový, což však není.

Neuzavřenost vůči doplňku plyne z uzavřenosti třídy bezkontextových jazyků vzhledem k operaci sjednocení, neuzavřenosti na průnik a De Morganových pravidel:

L_1 \cap L_2 = \neg(\neg L_1 \cup \neg L_2)

Předměty

Vypracoval

Marek Menšík UČO 255679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů.

Použitá literatura a weby

1)
Přitom každá regulární gramatika je současně i bezkontextová, tedy pouhé nalezení bezkontextové gramatiky ještě nemusí znamenat, že jazyk není navíc i regulární.
2)
skripta Automaty a formální jazyky I, str. 77
3) , 4) , 5)
skripta Automaty a formální jazyky I, str. 78
6)
skripta Automaty a formální jazyky I, str. 78
7)
Web IB102 - slajdy10, str. 5 a 8
8)
skripta Formální jazyky a automaty I, str. 86
9) , 11)
skripta Formální jazyky a automaty I, str. 83
10)
skripta Formální jazyky a automaty I, str. 89
12)
str. 84 skripta Formální jazyky a automaty I, slajdy11 - str. 12
13)
skripta Formální jazyky a automaty I, str. 90
14)
slajdy11, str. 17