AP10, IN10 Bezkontextové jazyky

Zadání

(definice, vlastnosti, způsoby jejich reprezentace, konstrukce bezkontextové gramatiky a zásobníkového automatu, normální formy bezkontextových gramatik, použití lematu o vkládání pro bezkontextové jazyky, uzávěrové vlastnosti bezkontextových jazyků)

Definice

Jazyk $L$ je bezkontextový, pokud existuje bezkontextová gramatika $G$ taková, že $L(G)=L$ .¹⁾ 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$ ).

Definici zásobníkového automatu je možné nalézt v otázce AP11,IN11 Zásobníkové automaty

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

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

Konstrukce bezkontextové gramatiky a zásobníkových automatů

Konstrukce zásobníkových automatů jsou popsány v otázce AP11,IN11 Zásobníkové automaty.
Každou bezkontextovou gramatiku, která reprezentuje neprázdný bezkontextový jazyk, lze dále upravit do tzv. kanonických tvarů - lépe se s nimi pracuje, jsou přehlednější, vyžadují je některé algoritmy atd. Kanonické tvary bezkontextových gramatik jsou následující:

redukované CFG
gramatiky bez $\epsilon$ -pravidel
gramatiky bez jednoduchých pravidel
gramatiky bez levé rekurze

Definice 3.7

Symbol $X \in N \cup \Sigma$ je nepoužitelný v CFG $G = (N, \Sigma, P, S)$ právě když v $G$ neexistuje derivace tvaru $S \Rightarrow^\ast wXy \Rightarrow^\ast wxy$ pro nějaká $w,x,y \in \Sigma^\ast$ .
Řekneme, že $G$ je redukovaná, jestliže neobsahuje žádné nepoužitelné symboly.

Nepoužitelnost typu I.: Neexistuje terminální řetěz $w$ takový, že $A \Rightarrow^\ast w$ .
Nepoužitelnost typu II.: Neexistují řetězy $x,y$ takové, že $S \Rightarrow^\ast xAy$ .

Definice 3.13

Řekneme, že CFG $G = (N, \Sigma, P, S)$ je bez $\epsilon$ -pravidel právě když buď

$P$ neobsahuje žádné $\epsilon$ -pravidlo (tj. pravidlo tvaru $A \rightarrow \epsilon$ ) nebo
v $P$ existuje právě jedno $\epsilon$ -pravidlo $S \rightarrow \epsilon$ a $S$ se nevyskytuje na pravé straně žádného pravidla z $P$ .

Jednoduchým pravidlem nazýváme každé pravidlo tvaru $A \rightarrow B$ , kde $A,B \in N$ .

Definice 3.17 a Věta 3.18

CFG $G = (N, \Sigma, P, S)$ se nazývá necyklická, právě když neexistuje $A \in N$ takový, že $A \Rightarrow^+ A$ .

$G$ se nazývá vlastní, právě když je bez nepoužitelných symbolů, bez $\epsilon$ -pravidel a necyklická.

Ke každému neprázdnému bezkontextovému jazyku existuje vlastní bezkontextová gramatika, která jej generuje.

Definice 3.28

Neterminál A v CFG $G = (N, \Sigma, P, S)$ se nazývá rekursivní jestliže v $G$ existuje derivace $A \Rightarrow^+ \alpha A\beta$ . Je-li $\alpha = \epsilon$ resp. $\beta = \epsilon$ , pak A se nazývá levorekursivní resp. pravorekursivní. CFG bez levorekursivních terminálů se nazývá nelevorekursivní. $\alpha , \beta$ jsou levé strany pravidel v P.

Osobně se domnívám, že otázka je dostatečně obsáhlá na to, aby při ní nebyla vyžadována znalost algoritmů na odstranění nepoužitelných symbolů, jednoduchých pravidel, levé rekurze atd. Pokud by někdo přeci jen chtěl tyto algoritmy nastudovat, nalezne je ve skriptech Formální jazyky a automaty, počínaje stranou 62 (=68 v pdf).

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.

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$ , $|z|>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$ .

Pokud by to někdo chtěl čistě matematicky pro „lehčí“ zapamatování:
$L \in CFL \Rightarrow \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 vlastně ve tvaru implikace. 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)$

Rozhodnutelné vlastnosti

Pro třídu bezkontextových jazyků jsou rozhodnutelné následující vlastnosti:

Problém příslušnosti: Ke každé CFG je možné sestrojit PDA a můžeme tak ověřit jestli daný PDA přijme nebo zamítne slovo w.
Problém prázdnosti: Stačí ověřit zda $S \in N_e$ . ( $N_e$ je množina použitelných symbolů vzhledem k typu I.)
Problém konečnosti: Ke každé CFG lze sestrojit čísla $m,n$ taková, že $L(G)$ je nekonečný, právě když existuje slovo $z \in L(G)$ takové, že $m<|z|<n$ ²⁾.

Poznámka

Lingvista Noam Chomsky rozdělil gramatiky do čtyř skupin (typů) na základě různých omezení na tvar pravidel a podle jejich popisné síly.

Chomského hierarchie rozlišuje tyto čtyři (základní) typy gramatik - viz Regulární jazyky - poznámka

Předměty

FI:IB005 Formální jazyky a automaty I prof. RNDr. Mojmír Křetínský, CSc.
FI:IB102 Automaty a gramatiky RNDr. Jan Strejček, Ph.D.

Zdroje

Skripta k IB005 Stránky prof. Křetínský Stránky Strejček

Vypracoval

Honza Palas, hotovo

Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

¹⁾

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

²⁾

Důkaz je uveden ve skriptech Formální jazyky a automaty I., strana 96

Obsah