Chomského normální forma bezkontextových gramatik

Do předmětu Teoretická informatika oboru Informační a komunikační technologie na VŠB jsem měl za úkol zpracovat krátký referát na téma Chomského normální forma bezkontextových gramatik. Nejde o žádnou vědeckou práci, ale i tak je mi líto nechat tento text ležet v šuplíku bez užitku někomu dalšímu. Celý text ke stažení.

Chomského normální forma je tvar či specifický způsob zápisu formální gramatiky. Při převodu bezkontextové gramatiky do Chomského normální formy se po odstranění pravidel typu A → ε provádí krok, který odstraňuje pravidla typu X → Y (neterminál se přepisuje na neterminál). (Pak dostaneme jen pravidla typu A → α, kde α je terminál nebo |α| ≥ 2, přičemž generovaný jazyk se nezměnil.)

Noan Chomsky - filosof a matematik

Zadání

Na vhodném příkladu ilustrujte algoritmus odstraňující ona pravidla X → Y a ukažte jeho korektnost.

Definice

Je přímo uvedena výše, jinými slovy: Bezkontextová gramatika je v Chomského normální formě, jestliže každé její pravidlo je tvaru X → Y Z nebo X → a, kde „X, Y, Z“ označují neterminální symboly a „a“ terminální symbol. Tedy na levé straně je jeden neterminál, na pravé terminál nebo maximálně 2 další neterminály. Kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem.

Tvar CHNF

A → BC nebo

A → α nebo

S → ε (je povoleno, pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla)

Algoritmus

odstranění ε pravidel;

nahrazení těmi terminály a neterminály, které by se tam mohly objevit a přidat je za stávající pravidla. Je třeba to provést důkladně a zahrnou všechny možné vzniknuvší kombinace!

odstranění jednoduchých pravidel;

samostatné neterminály v jednom znaku nahradit jejich přepisem

odstranění terminálů mimo A → α;

zavést substituci novým neterminálem za všechny terminály, které jsou součástí neterminálů, kromě osamocených terminálů nebo skupiny terminálů.

pohlcování neterminálních symbolů.

Všechny neterminály, které jsou delší než 2 znaky se musí zkrátit zavedením dalších substitucí. Ponechá se první znak a zbývající se substituují dalším neterminálem.

Výsledkem je sada pravidel ve tvaru X → Y Z, přičemž pro zjednodušení mohou být zapsána i za sebou se znakem „nebo |“.

Příklady

Použití

Bezkontextové gramatiky

G = ({VÝROK, PŘÍVLASTEK, PODMĚT, PŘÍSUDEK}, {malý, velký, pes, kocour, běží, leží, spí}, VÝROK, P_dále)

Význam

Pro pochopení formy je třeba mít představu o tom, čeho forma to je. S bezkontextovými jazyky a gramatikami se hojně setkáváme při syntaktické analýze textu, třeba zdrojových kódů programovacích jazyků. Slovo „bezkontextová“ v názvu gramatiky znamená, že na levé straně každého pravidla stojí jeden neterminál bez sousedních symbolů (tedy není v „kontextu“).

Všechny bezkontextové jazyky lze generovat bezkontextovými gramatikami v jistém speciálním tvaru. Derivační stromy, příslušné k těmto gramatikám, pak mají jednotný tvar. Tato skutečnost usnadňuje cestu k závěrům v některých úvahách o bezkontextových jazycích. Příkladem je Chomského nebo Greibachova normalní forma.

Převedení zápisu gramatiky do CHNF vede k vytvoření jednoznačného derivačního stromu. Gramatika G je jednoznačná, jestliže každé slovo z L(G) má právě jedno levé odvození (právě jeden derivační strom), jinak je víceznačná a jako takovou ji není možné vždy transformovat na ekvivalentní jednoznačnou gramatiku.

Hlavní výhodou v Chomského normální formě je že, každé odvození řetězce s n písmeny má přesně 2n - 1 kroků, je tedy možné určit, zda je řetězec v jazyku všech derivací ve známém počtu operací.

Derivační strom

Derivační strom je v reprezentant syntaktické struktury slovního řetězce podle formální gramatiky. V derivačním stromě jsou vnitřní uzly označeny jako neterminály gramatiky, zatímco koncové uzly jsou označeny jako terminály. Derivační stromy mohou být využity pro generování nebo analýzu vět v přirozeném jazyce, stejně tak jako během zpracování počítačových jazyků.

Vytváření derivačních stromů ze specificky formátované gramatiky vede na jednoznačné derivační stromy, což je velký výhoda pro porovnávání bezkontextových gramatik mezi sebou.

Důkaz

Nejprve věta 12.2.2 o odstranitelnosti ε přechodů: Ke každé bezkontextové gramatice G lze sestrojit ekvivalentní nevypouštějící gramatiku G‘ tž. L(G‘) = L(G) − {ε}. Důkaz ve skriptech str. 62.

Co se tím říká? Nedochází k porušení správnosti gramatiky, neboť důkaz odstranění ε přechodů se provádí výše, to je první zásah do konstrukce gramatiky: ve stručnosti se pouze přepisují symboly na nová umístění, ale jde jen komplikaci zápisu. Dalším porušením integrity by mohlo být přepisování pravidel neterminály, ale lze jistě souhlasit, že zavedením substituce nedochází ke změně významu původního výrazu a právě tato úprava se v průběhu převodu do CHNF odehrává. Intuitivně lze vyčíst, že v rámci algoritmu nedochází k modifikaci samotné gramatiky.

Jednoduše si lze představit důkaz jako problém grafu o 2 uzlech nad sebou. Pokud horní a spodní uzel rozdělím a vložím mězi ně uzel další, pak se zcela logicky nemění význam grafu, pouze je v něm více uzlů. Přesně stejný případ vytváří gramatika v Chomského normální formě, protože nemění význam a pouze dochází k přidání pravidel se specifickými vlastnostmi.