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$ .¹⁾

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:

bezkontextovou gramatikou
zásobníkovým automatem
rozšířeným zásobníkovým automatem

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 ²⁾

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 q₁
$\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 ³⁾

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í ⁴⁾

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, ⁵⁾

$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 ⁶⁾, konstrukce viz slidy ⁷⁾

Grafická reprezentace konfigurací

Zpravidla nekonečné
Vnitřní konfigurace (= částečná konfigurace) = aktuální stav a celý obsah zásobníku (vrchol se píše vlevo)

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ů:

$A \rightarrow BC,\ B,C\in N$
$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 ⁸⁾

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 ⁹⁾

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 ¹⁰⁾

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 ¹¹⁾

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

V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou $X_{1} ...X_{n}$ nějakého A-pravidla.
V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem $X_{1} ...X_{n}$ .

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

$\delta(q, \varepsilon, A)$ obsahuje $(q, \alpha)$ právě když $A \rightarrow \alpha \in P$
$\delta(q, a, a) = \lbrace(q, \varepsilon)\rbrace$ pro všechna $a \in \Sigma$

korektnost + důkaz viz skripta ¹²⁾

Nedeterministická syntaktická analýza zdola nahoru

Lemma 3.55 ¹³⁾

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:

může kdykoli číst do zásobníku vstupní symbol,
(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:

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

korektnost viz slajdy ¹⁴⁾

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í:

levou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA, pravou stranu pravidel z gram. na zásobník pravé strany

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

„mazací“ přechodové fce

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

Akceptující výpočet nad slovem abababaa:

(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í:

terminály z gramatiky se předávají na zásobník

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

pravou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA, levou stranu pravidel z gram. na zásobník pravé strany

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

přechod do koncového stavu

$\delta$ (q, $\varepsilon$ , $\bot$ S) = {(r, $\varepsilon$ )}

Akceptující výpočet nad slovem abababaa:

(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ů:

$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$ .
$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:

sjednocení
zřetězení
iterace
pozitivní iterace
průnik s regulárním jazykem

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

průnik
doplněk

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

¹⁾

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í.

²⁾

skripta Automaty a formální jazyky I, str. 77

³⁾ , ⁴⁾ , ⁵⁾

skripta Automaty a formální jazyky I, str. 78

⁶⁾