Chomsky normální forma - Chomsky normal form
v formální jazyk teorie, a bezkontextová gramatika, G, se říká, že je v Chomsky normální forma (poprvé popsal Noam Chomsky )[1] pokud všechny výrobní pravidla jsou ve tvaru:[Citace je zapotřebí ]
- A → před naším letopočtemnebo
- A → Anebo
- S → ε,
kde A, B, a C jsou neterminální symboly, dopis A je symbol terminálu (symbol, který představuje konstantní hodnotu), S je počáteční symbol a ε označuje prázdný řetězec. Také ani jeden B ani C může být počáteční symbol a třetí produkční pravidlo se může zobrazit pouze v případě, že je ε L(G), jazyk vytvořený bezkontextovou gramatikou G.[2]:92–93,106
Každá gramatika v Chomského normální formě je bez kontextu, a naopak, každá bezkontextová gramatika může být transformována do ekvivalent jeden[poznámka 1] který je v Chomského normální formě a má velikost ne větší než čtverec velikosti původní gramatiky.
Převod gramatiky do Chomského normální formy
Chcete-li převést gramatiku na Chomského normální formu, použije se v jednoduchém pořadí posloupnost jednoduchých transformací; toto je popsáno ve většině učebnic o teorii automatů.[2]:87–94[3][4][5]Prezentace zde navazuje na Hopcroft, Ullman (1979), ale je přizpůsobena pro použití názvů transformací od Lange, Leiß (2009).[6][poznámka 2] Každá z následujících transformací zavádí jednu z vlastností požadovaných pro Chomského normální tvar.
START: Odstraňte počáteční symbol z pravé strany
Představte nový počáteční symbol S0a nové pravidlo
- S0 → S,
kde S je předchozí počáteční symbol. To nemění gramatiku vytvořeného jazyka a S0 nenastane na pravé straně žádného pravidla.
TERMÍN: Eliminujte pravidla pomocí neolitických terminálů
Odstranit každé pravidlo
- A → X1 ... A ... Xn
se symbolem terminálu A protože nejste jediným symbolem na pravé straně, zavést pro každý takový terminál nový neterminální symbol NAa nové pravidlo
- NA → A.
Změňte každé pravidlo
- A → X1 ... A ... Xn
na
- A → X1 ... NA ... Xn.
Pokud se na pravé straně objeví několik terminálních symbolů, nahraďte je každý současně příslušným neterminálním symbolem. Tím se nezmění vytvořený jazyk gramatiky.[2]:92
BIN: Odstraňte pravé strany s více než 2 neterminály
Vyměňte každé pravidlo
- A → X1 X2 ... Xn
s více než 2 neterminály X1,...,Xn podle pravidel
- A → X1 A1,
- A1 → X2 A2,
- ... ,
- An-2 → Xn-1 Xn,
kde Ai jsou nové neterminální symboly. To opět nemění produkovaný jazyk gramatiky.[2]:93
DEL: Odstraňte pravidla ε
Ε-pravidlo je pravidlo formy
- A → ε,
kde A není S0, počáteční symbol gramatiky.
Chcete-li vyloučit všechna pravidla tohoto formuláře, nejprve určete množinu všech neterminálů, které odvozují ε. Hopcroft a Ullman (1979) nazývají takové neterminály s možnou hodnotou Nulla spočítejte je takto:
- Pokud pravidlo A → Existuje tedy ε A je s možnou hodnotou Null.
- Pokud pravidlo A → X1 ... Xn existuje a každý Xi je tedy nulová A má také povolenou hodnotu Null.
Nahraďte každé pravidlo a získáte střední gramatiku
- A → X1 ... Xn
všemi verzemi s některými s možnou hodnotou Null Xi Vymazáním každého pravidla ε v této gramatice se získá transformovaná gramatika, pokud není její levá strana počátečním symbolem.[2]:90
Například v následující gramatice se symbolem začátku S0,
- S0 → AbB | C
- B → AA | AC
- C → b | C
- A → A | ε
neterminál A, a tedy také B, je s možnou hodnotou Null, zatímco žádný z nich C ani S0 is. Proto je získána následující střední gramatika:[Poznámka 3]
- S0 → AbB | Ab
B|AbB |AbB| C - B → AA |
AA | AA|AεA| AC |AC - C → b | C
- A → A | ε
V této gramatice byla všechna pravidla εpodtrženo na místě volání ".[poznámka 4]V dalším kroku je tedy lze odstranit, čímž se získá gramatika:
- S0 → AbB | Ab | bB | b | C
- B → AA | A | AC | C
- C → b | C
- A → A
Tato gramatika vytváří stejný jazyk jako původní vzorová gramatika, viz. {ab,aba,abaa,abab,abac,abb,abc,b,bab,bac,bb,před naším letopočtem,C}, ale nemá žádná pravidla ε.
UNIT: Eliminate unit rules
Pravidlo jednotky je pravidlo formy
- A → B,
kde A, B jsou neterminální symboly. Chcete-li jej odstranit, pro každé pravidlo
- B → X1 ... Xn,
kde X1 ... Xn je řetězec neterminálů a terminálů, přidat pravidlo
- A → X1 ... Xn
pokud se nejedná o pravidlo jednotky, které již bylo (nebo právě je) odstraněno.
Pořadí transformací
Proměna X vždy zachovává ( ) resp. může zničit ( ) výsledek Y: | |||||
Y X | START | OBDOBÍ | ZÁSOBNÍK | DEL | JEDNOTKA |
---|---|---|---|---|---|
START | |||||
OBDOBÍ | |||||
ZÁSOBNÍK | |||||
DEL | |||||
JEDNOTKA | ( | )*||||
*JEDNOTKA zachovává výsledek DEL -li START byl zavolán dříve. |
Při výběru pořadí, ve kterém mají být výše uvedené transformace použity, je třeba vzít v úvahu, že některé transformace mohou zničit výsledek dosažený jinými. Například, START znovu zavede pravidlo jednotky, pokud se použije po JEDNOTKA. Tabulka ukazuje, které objednávky jsou přijaty.
Navíc nejhorší nafouknutí ve velikosti gramatiky[poznámka 5] závisí na pořadí transformace. Pomocí |G| k označení velikosti původní gramatiky G, velikost nafouknutí v nejhorším případě se může pohybovat od |G|2 až 22 | G |, v závislosti na použitém transformačním algoritmu.[6]:7 Vyhodnocení velikosti gramatiky závisí na pořadí mezi nimi DEL a ZÁSOBNÍK. Může to být exponenciální, když DEL se provádí jako první, ale jinak je lineární. JEDNOTKA může dojít ke kvadratickému zvětšení velikosti gramatiky.[6]:5 Objednávky START,OBDOBÍ,ZÁSOBNÍK,DEL,JEDNOTKA a START,ZÁSOBNÍK,DEL,JEDNOTKA,OBDOBÍ vést k nejmenšímu (tj. kvadratickému) nafouknutí.
Příklad
Následující gramatika se symbolem začátku Expr, popisuje zjednodušenou verzi sady všech syntakticky platných aritmetických výrazů v programovacích jazycích jako C nebo Algol60. Oba číslo a proměnná jsou zde pro jednoduchost považovány za koncové symboly, protože v a kompilátor front-end jejich vnitřní struktura obvykle není zohledněna analyzátor. Symbol terminálu „^“ označen umocňování v Algol60.
Expr → Období | Expr AddOp Období | AddOp Období Období → Faktor | Období MulOp Faktor Faktor → Hlavní | Faktor ^ Hlavní Hlavní → číslo | proměnná | ( Expr ) AddOp → + | − MulOp → * | /
V kroku "START" z výše konverzní algoritmus, jen pravidlo S0→Expr je přidán do gramatiky. Po kroku „TERM“ vypadá gramatika takto:
S0 → Expr Expr → Období | Expr AddOp Období | AddOp Období Období → Faktor | Období MulOp Faktor Faktor → Hlavní | Faktor PowOp Hlavní Hlavní → číslo | proměnná | Otevřeno Expr Zavřít AddOp → + | − MulOp → * | / PowOp → ^ Otevřeno → ( Zavřít → )
Po kroku „BIN“ se získá následující gramatika:
S0 → Expr Expr → Období | Expr AddOp_Term | AddOp Období Období → Faktor | Období MulOp_Factor Faktor → Hlavní | Faktor PowOp_Primary Hlavní → číslo | proměnná | Otevřeno Expr_Close AddOp → + | − MulOp → * | / PowOp → ^ Otevřeno → ( Zavřít → ) AddOp_Term → AddOp Období MulOp_Factor → MulOp Faktor PowOp_Primary → PowOp Hlavní Expr_Close → Expr Zavřít
Protože neexistují žádná pravidla ε, krok „DEL“ gramatiku nezmění. Po kroku „UNIT“ se získá následující gramatika, která je v Chomského normálním tvaru:
S0 → číslo | proměnná | Otevřeno Expr_Close | Faktor PowOp_Primary | Období MulOp_Factor | Expr AddOp_Term | AddOp Období Expr → číslo | proměnná | Otevřeno Expr_Close | Faktor PowOp_Primary | Období MulOp_Factor | Expr AddOp_Term | AddOp Období Období → číslo | proměnná | Otevřeno Expr_Close | Faktor PowOp_Primary | Období MulOp_Factor Faktor → číslo | proměnná | Otevřeno Expr_Close | Faktor PowOp_Primary Hlavní → číslo | proměnná | Otevřeno Expr_Close AddOp → + | − MulOp → * | / PowOp → ^ Otevřeno → ( Zavřít → ) AddOp_Term → AddOp Období MulOp_Factor → MulOp Faktor PowOp_Primary → PowOp Hlavní Expr_Close → Expr Zavřít
The NA zavedené v kroku „TERMÍN“ jsou PowOp, Otevřeno, a Zavřít.v Ai zavedené v kroku "BIN" jsou AddOp_Term, MulOp_Factor, PowOp_Primary, a Expr_Close.
Alternativní definice
Chomsky snížená forma
Jiná cesta[2]:92[7] definovat Chomského normální tvar je:
A formální gramatika je v Chomsky snížená forma pokud jsou všechna jeho produkční pravidla ve formě:
- nebo
- ,
kde , a jsou neterminální symboly a je symbol terminálu. Při použití této definice nebo může být počáteční symbol. Pouze ty bezkontextové gramatiky, které negenerují prázdný řetězec lze transformovat do Chomského redukované formy.
Floyd normální forma
V dopise, kde navrhl termín Backus – Naurova forma (BNF), Donald E. Knuth implikovaná BNF "syntax, ve které mají všechny definice takovou formu, lze říci, že je v" Floyd Normal Form "",
- nebo
- nebo
- ,
kde , a jsou neterminální symboly a je symbol terminálu,protože Robert W. Floyd nalezena jakákoli syntaxe BNF může být převedena na výše uvedenou v roce 1961.[8] Tento termín však stáhl, „jelikož mnoho lidí nepochybně tento jednoduchý fakt nezávisle použilo ve své vlastní práci, a jde pouze o vedlejší myšlenky Floydovy poznámky.“[9] Zatímco Floydova poznámka cituje Chomského původní článek z roku 1959, Knuthův dopis ne.
aplikace
Kromě teoretického významu se konverze CNF používá v některých algoritmech jako krok předzpracování, např Algoritmus CYK, a analýza zdola nahoru pro bezkontextové gramatiky a jeho variantní pravděpodobnostní CKY.[10]
Viz také
- Backus – Naurova forma
- Algoritmus CYK
- Greibachova normální forma
- Kuroda normální forma
- Čerpání lemmatu pro bezkontextové jazyky - jeho důkaz se opírá o Chomského normální formu
Poznámky
- ^ tj. ten, který produkuje to samé Jazyk
- ^ Například sloučení Hopcroft, Ullman (1979) OBDOBÍ a ZÁSOBNÍK do jedné transformace.
- ^ označující ponechaný a vynechaný neterminál N podle N a
N, resp - ^ Pokud by gramatika měla pravidlo S0 → ε, nemohlo být „vloženo“, protože nemělo žádné „stránky volání“. V dalším kroku jej proto nebylo možné odstranit.
- ^ tj. psaná délka, měřená v symbolech
Reference
- ^ Chomsky, Noam (1959). „O určitých formálních vlastnostech gramatik“. Informace a kontrola. 2 (2): 137–167. doi:10.1016 / S0019-9958 (59) 90362-6. Tady: Oddíl 6, s. 152ff.
- ^ A b C d E F Hopcroft, John E .; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8.
- ^ Hopcroft, John E .; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Úvod do teorie automatů, jazyků a výpočtu (3. vyd.). Addison-Wesley. ISBN 978-0-321-45536-9. Oddíl 7.1.5, s. 272
- ^ Rich, Elaine (2007). Automaty, vypočítatelnost a složitost: teorie a aplikace (1. vyd.). Prentice-Hall. ISBN 978-0132288064.[stránka potřebná ]
- ^ Wegener, Ingo (1993). Theoretische Informatik - Eine algorithmenorientierte Einführung. Leitfäden und Mongraphien der Informatik (v němčině). Stuttgart: B. G. Teubner. ISBN 978-3-519-02123-0. Sekce 6.2 „Die Chomsky-Normalform für kontextfreie Grammatiken“, s. 149–152
- ^ A b C Lange, Martin; Leiß, Hans (2009). „Do CNF nebo ne do CNF? Efektivní, přesto prezentovatelná verze algoritmu CYK“ (PDF). Informatica Didactica. 8.
- ^ Hopcroft a kol. (2006)[stránka potřebná ]
- ^ Floyd, Robert W. (1961). „Poznámka k matematické indukci ve gramatických strukturách fráze“ (PDF). Informace a kontrola. 4 (4): 353–358. doi:10.1016 / S0019-9958 (61) 80052-1. Zde: str.354
- ^ Knuth, Donald E. (prosinec 1964). "Backus normální forma vs. Backus Naur forma". Komunikace ACM. 7 (12): 735–736. doi:10.1145/355588.365140. S2CID 47537431.
- ^ Jurafsky, Daniel; Martin, James H. (2008). Zpracování řeči a jazyka (2. vyd.). Pearson Prentice Hall. p. 465. ISBN 978-0-13-187321-6.
Další čtení
- Cole, Richarde. Převod CFG na CNF (Chomsky normální forma), 17. října 2007. (pdf) - používá objednávku TERM, BIN, START, DEL, UNIT.
- John Martin (2003). Úvod do jazyků a teorie výpočtu. McGraw Hill. ISBN 978-0-07-232200-2. (Strany 237–240 v oddíle 6.6: zjednodušené a normální formuláře.)
- Michael Sipser (1997). Úvod do teorie výpočtu. PWS Publishing. ISBN 978-0-534-94728-6. (Stránky 98–101 v části 2.1: bezkontextové gramatiky. Strana 156.)
- Sipser, Michael. Úvod do teorie výpočtu 2. vydání.
- Alexander Meduna (6. prosince 2012). Automaty a jazyky: Teorie a aplikace. Springer Science & Business Media. ISBN 978-1-4471-0501-5.