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

Diskuze

Roman Plášil, 2008/06/14 18:45

Opravil jsem chybu v sekci Průnik a doplněk – ty dva jazyky co tam byly předtím to moc neilustrovaly, protože byly totožné :)

Marek Babák, 2008/06/17 11:53

Nějak nechápu jak ze z a^n b^n c^m a a^m b^n c^m dostane průnikem a^n b^n c^n ? Je to chyba na mém přijímači? Pokud ano tak prosím zdůvodnění

Roman Plášil, 2008/06/21 23:35

Aby to bylo v a^n b^n c^m, musí to mít stejný počet a jako b. Aby to bylo v tom druhém, musí to mít stejný počet a a c. Aby to bylo v průniku, musí to mít stejný počet a a b && stejný počet a a c. Z tranzitivity relace „stejný počet“ plyne, že tam musí být všech písmen stejně.

Marek Babák, 2008/06/17 12:02

Pár drobností:

mluví se tu o gramatikách v nejrůznějších formách a není tu příklad ani jedné (jednoduchý napoví)
v definici 3.28 se používá symbol beta a není zřejmé, zda se jím myslí terminál, neterminál nebo obojí
kousek pod definicí 3.28 je odkaz na skripta na stranu XX, prosím o nahrazení proměnné její hodnotou :)
na konci se používá termín PDA, ale není tu o něm ani slovo(ano, je v 11, ale lepší by asi bylo napsat zásobníkový atm.)
v problému konečnosti je nějaký symbol, který přesně nevím co má znamenat?

Pár věcí, které se mi prohnaly hlavou při učení, prosím někoho o upřesnění/potvrzení ať pak neplácám u zkoušky kraviny:

u CNF buď nemusí být třetí bod(vyplývá z definice gramatiky bez epsilon pravidel), nebo by tam mělo být i omezení, že S nemůže být na pravé straně?
Lze u GNF říct, že je bez epsilon pravidel a je pravorekursivní?

Marek Babák, 2008/06/17 17:24

Stranu XX jsem dopsal, stejně tak jako odkaz na skripta, trochu jsem upravil definici rekursivnosti jazyka a přidal čistě matematickou definici pumping pro všechny všechny, které nebaví psát.
U GNF je ve skripetch poznámka, že se jedná o absenci epsilon pravidel ve smyslu definice(3.7), takže i v GNF imho může být S → epsilon, totéž u CNF, takže jsem to upravil.

Jan Palas, 2008/06/17 23:52

Ahoj, omlouvám se, že jsem nereagoval na připomínky, byl jsem týden ve Finsku bez internetu. Nicméně na svoji „obranu“ uvedu to, že já jsem otázku neoznačil za hotovou (zřejmě to udělal někdo za mě) - některé věci jsem měl v plánu dodělat (např. odkazy na literaturu, strana XX :), atd. )

Takže teď zareaguji pouze na aktuální připomínky:

- v problému konečnosti nevím, jaký symbol máš na mysli. Pokud je tím symbol absolutní hodnoty,tak znamená délku slova

- symboly jako alfa a beta atd. se používají pro neterminály sjednocené s terminály - doplním

- a neodpustím si jedno rýpnutí: Snad tohle není bakalářka, abych musel každý pojem před použitím definovat, ne? :) Jestli někdo neví, co znamená PDA u otázky o týkající se také zásobníkových automatů, tak nevim, nevim… :) Vždyť se tyhle teoretické otázky snad nedají naučit (pochopit) jen z toho, co je vypíchnuto tedy na wiki? Pletu se nebo jsem v menšině, když se učím i ze skript/slidů?

Jinak zbylé připomínky zapracuji co nejdříve.

Zly pes, 2008/06/21 16:21

heh…len pomocou wiki isto nie :-) ..ako som zvedavy co budu naozaj vyzadovat pri ustnych a akou formou sa to teda ma clovek ucit(opakovat), ono kym si clovek spomenie ako funguje P.L. pre CFL alebo nejake tie algoritmy, tak to vie zabrat cas a zas naucit sa len cisto formulku mi potom prestava davat vyznam naco sa to vobec ucim (basnicky)..a ked to zase chces zopaknut aby si vobec vedel pri kazdej otazke o com tocis, tak mi pridu tie niektore otazky velmo obsiahle..(to fakt nestiham absorbovat..nieto este mysliet akou formou prezentovat otazku)..

Tomáš Kopecký, 2008/06/18 00:46

V popise algoritmu převodu CFG do Chomského normální formy je místo správného _neterminálem_ použito _terminálem_. (Někdo z registrovaných to pls opravte, ať to někoho nezmate..)

„Pro pravé strany délky 2, které se skládají z terminálu a neterminálu nahradí terminál novým _terminálem_. Např. X → aC se změní na X → <a>C, <a> → a.“

Adam Libuša, 2008/06/18 12:45

Done..

Roman Plášil, 2008/06/22 10:08

Opravil jsem ten matematický zápis PL. Teď jsem si všimnul, že ve skriptech mají něco podobného, jako tam bylo předtím. Ono záleží na tom, jak se přesně ty kvantifikátory a ty čárky v tom zápise interpretují. Nejlepší by asi bylo to napsat podle opravdové syntaxe predikátové logiky.

You could leave a comment if you were logged in.

home/inf/ap10.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru

Obsah