V teoretické informatice , a zejména v teorii jazyků , je bezkontextová gramatika v Chomského normální formě právě tehdy, pokud jsou všechna její produkční pravidla ve formě:
kde jsou nekoncové symboly , je koncový symbol , je axiom gramatiky a je prázdné slovo.
Pokud je přítomno poslední pravidlo, je požadováno, aby se axiom nikdy neobjevil ve správném členu pravidla.
Běžná forma Chomského je pojmenována podle amerického lingvistu Noama Chomského , který také navrhl hierarchii, která nese jeho jméno , a který tuto normální podobu popsal při této příležitosti v článku publikovaném v roce 1959 .
Varianta definice spočívá v nepovolení prázdného slova: pouze pravidla formuláře
nebo ,jsou povoleny, kde , a non-terminální symboly a je symbol terminál . Toto je definice přijatá například Cartonem nebo Hopcroftem et. al. . Tyto gramatiky samozřejmě negenerují prázdné slovo.
Další varianta vyžaduje, aby přímé členy pravidel měly délku nejvýše 2, ale nevyžaduje, aby přímé členy délky 2 byly tvořeny výhradně z nekoncových symbolů. Taková gramatika se nazývá 2-normální forma nebo „2NF“.
Jakákoli gramatika napsaná v Chomského normální formě je gramatika bez kontextu . Naopak jakoukoli gramatiku mimo kontext lze převést na ekvivalentní gramatiku (tj. Generující stejný jazyk) v Chomského normální podobě.
S výjimkou pravidla (3) se všechna pravidla gramatiky v Chomského normální formě zvyšují; v průběhu derivace se proto délky slov zvyšují. Zvyšují se o 1 s pravidlem typu (1) a zůstávají stejně dlouhé s pravidlem typu (2). Odvození slova délky se proto vždy provádí v krocích: existují kroky typu (1) a kroky typu (2). Kromě toho, protože všechna pravidla, která nevycházejí z terminálu, transformují jeden neterminál na dva neterminály, je derivační strom založený na gramatice Chomského normálního tvaru binární strom s vnitřními uzly a listy a jeho výška je nanejvýš délkou řetězec znaků.
Díky těmto vlastnostem se mnoho důkazů v oblasti formálních jazyků zjednodušuje pomocí Chomského normální formy (například skutečnost, že je rozhodující příslušnost slova ve generovaném jazyce). Několik běžných algoritmů syntaktické analýzy, jako je algoritmus Cocke-Younger-Kasami , používá tuto normální formu.
Konverze gramatiky do Chomského normální formy se provádí řadou jednoduchých transformací aplikovaných v určitém pořadí. Většina učebnic teorie automatů popisuje tento převod. Ve vzdělávacím článku Lange a Leiß pečlivě popisují tyto operace a pojmenovávají fáze transformace, které usnadňují expozici. Kromě toho označují pořadí použití, které zaručuje lineární složitost.
Obecně transformaci předchází operace - zvaná „redukce“ v Cartonu 2008 (část 2.1.2: Redukované gramatiky , str. 79 ) nebo „eliminace zbytečných symbolů“ v Hopcroft, Motwani a Ullman 2007 , (část 7.1. 1: Eliminating zbytečné symboly , str. 262 ) - který slouží k odstranění nepotřebných proměnných. Proměnná X je užitečná, pokud se objeví v derivaci axiomu v terminálním slově; za tímto účelem musí být přístupný z axiomu řadou derivací a musí být „společně přístupný“ v tom smyslu, že musí být schopen být odvozen terminálním slovem.
Každá z následujících pěti transformací ( START , TERM , BIN , DEL , UNIT ) zavádí jednu z vlastností požadovaných Chomského normální formou. Představujeme je v návaznosti na Langeho a Leisi, jako by se vztahovali na obecnou gramatiku; uvidíme později, že pořadí aplikace je důležité, pokud chceme minimalizovat časovou složitost. V těchto konkrétních objednávkách jsou některé operace jednodušší, například operace UNIT, která se používá k odstranění pravidel jednotky.
Složitost operací se měří ve vztahu k velikosti dané gramatiky G. Je definována jednoduše jako místo, které zaujímá psaní pravidel
kde předvolání zahrnuje všechna pravidla gramatiky. Zejména pravidlo ε přispívá k 1 v součtu.
Za tímto účelem zavedeme nový symbol, který se stane axiomem a pravidlem
,kde je starý axiom. To nemění vygenerovaný jazyk a proměnná se neobjeví v pravém členu pravidla.
Pokud se písmeno terminálu objeví v pravém členu pravidla délky alespoň 2, nahraďte jej novým a přidejte nové pravidlo
a výše uvedené pravidlo nahradíme
Ve skutečnosti tuto náhradu provádíme současně pro všechny výskyty koncových písmen ve správných členech pravidel. To nemění generovaný jazyk a zvyšuje počet pravidel o maximálně počet terminálových písmen. Operace je proto lineární jako funkce | G |.
Nahradíme pravidlo
,podle pravidel
,kde jsou nové neterminální symboly. Tato operace maximálně ztrojnásobuje gramatiku.
Ε-pravidlo je pravidlo formy
,kde není axiom gramatiky. Začneme určením proměnných, které jsou odvozeny v ε; tyto proměnné, nazývané voidable (v angličtině „nullable“), se počítají podle opakování: X je zrušitelné, pokud existuje pravidlo
takové, které jsou všechny zrušitelné.Pro libovolnou proměnnou , zrušitelnou či nikoli, jakékoli pravidlo
je nahrazeno všemi pravidly získanými odstraněním jedné nebo více nebo dokonce všech zrušitelných proměnných ve správném členu pravidla, pak odstraníme všechna pravidla ε (s výjimkou axiomu, pokud je přítomen).
Například v následující gramatice s axiomem S 0 ,
S 0 → AbB | VS B → AA | AC C → b | vs. A → a | εProměnná A , a tedy B , jsou zrušitelné a ani C, ani S 0 nejsou. V následující přechodné verzi byly proměnné, které mají být odstraněny, vybarveny:
S 0 → AbB | A bB | Ab B | A b B | VS B → AA | A A | A A | A ε A | AC | A C. C → b | vs. A → a | εPo odstranění žlutých proměnných a pravidel A → ε (původní) a B → ε (vytvořené) získáme gramatiku
S 0 → AbB | Ab | bB | b | VS B → AA | A | AC | VS C → b | vs. A → aTato gramatika generuje stejný jazyk bez pravidel ε.
Pravidlo jednota je pravidlo ve tvaru
kde a jsou proměnné a obecněji pravidlo
,kde všechny proměnné jsou zrušitelné. Abychom tento typ pravidla vyloučili, nahradíme jej pravidlem
pro každé pravidlo
pokud se nejedná o dříve odstraněné pravidlo jednotky. Tato technika je dokončena v případě cyklů (například existence tří pravidel ) identifikací proměnných cyklu: všechny jsou nahrazeny jednou z nich. Transformace UNIT může změnit velikost gramatiky z | G | do | G | 2 .
Zachování vlastností transformací | |||||
---|---|---|---|---|---|
✓ zpracování X zachovává výsledek Y ✗ zpracování X se může měnit výsledek Y . | |||||
X \ Y | START | OBDOBÍ | ZÁSOBNÍK | části | JEDNOTKA |
START | ✓ | ✓ | ✓ | ✗ | |
OBDOBÍ | ✓ | ✗ | ✓ | ✓ | |
ZÁSOBNÍK | ✓ | ✓ | ✓ | ✓ | |
části | ✓ | ✓ | ✓ | ✗ | |
JEDNOTKA | ✓ | ✓ | ✓ | ( ✓ ) * | |
* JEDNOTKA uchová výsledek DEL, pokud již byl proveden START . |
Pořadí, ve kterém jsou operace použity, je důležité ze dvou důvodů: zaprvé je možné, že by transformace mohla vyvrátit účinek předchozí operace; například pokud použijeme START po JEDNOTCE , znovu zavedeme pravidlo jednotky. Na tabulce jsou uvedeny příslušné objednávky.
Dalším důvodem pro výběr pořadí operací s opatrností je možné zvýšení velikosti gramatiky, a tím i složitost operací. Velikost výsledné gramatiky se může pohybovat od | G | 2 až 2 2 | G | pro gramatiku velikosti | G |. Zvýšení závisí na pořadí mezi DEL a BIN . Může být exponenciální, pokud se nejprve použije DEL , protože pravidlo, jehož pravá strana má délku n, může vytvořit 2 2 n pravidel a jinak je lineární. UNIT může způsobit kvadratické zvýšení výšky.
K nejmenšímu zvětšení velikosti dochází u objednávek ( START , TERM , BIN , DEL , UNIT ) a ( START , BIN , DEL , UNIT , TERM ).
Různé učebnice a kurzy jazykové teorie obecně obsahují kromě prezentace postupů také ukázky správnosti algoritmů. Formalizace těchto redukčních operací, konkrétně odstranění nepotřebných proměnných, odstranění pravidel jednotek a pravidel epsilon v asistentovi Coq proof, se ujali Marcus VM Ramos a Ruy JGB de Queiroz. V tomto formalismu Coq dokazuje, že operace jsou správné v tom smyslu, že zachovávají jazyk generovaný gramatikou.
Vzdělávací nástroj pro převod gramatiky do Chomského normální formy