Kurodova normální forma

Technology

12 hours ago

Author

Kurodova normální forma je tvar formální gramatiky, ve které jsou všechna odvozovací pravidla tvaru: :AB → CD :A → BC :A → B :A → a

kde A, B, C a D jsou neterminální symboly, a je terminální symbol. Někteří autoři nepřipouštějí pravidla tvaru A → B.

Pro gramatiky tohoto tvaru používal Sige-Yuki Kuroda a několik dalších autorů původně název lineární omezená gramatika .

Vlastnosti

Každá gramatika v Kurodově normální formě je monotonní a proto generuje kontextový jazyk. Naopak každý kontextový jazyk, který neobsahuje prázdný řetězec, lze generovat gramatikou v Kurodově normální formě

György Révész popsal jednoduchý způsob transformace gramatiky v Kurodově formě na Chomského kontextovou gramatiku: Pravidla tvaru AB → CD jsou nahrazena čtyřmi kontextovými pravidly AB → AZ, AZ → WZ, WZ → WD a WD → CD. Tímto způsobem lze dokázat, že každá monotónní gramatika je kontextová.

Příbuzné normální formy

Kurodova normální forma pro obecné gramatiky

Pro obecné frazové gramatiky existuje podobná normální forma, kterou někteří autoři nazývají také „Kurodova normální forma“: :AB → CD :A → BC :A → a :A → ε

kde ε je prázdný řetězec. Každá obecná frazová gramatika je slabě ekvivalentní s gramatikou tohoto tvaru.

Kurodova normální forma pro bezkontextové gramatiky

Gramatika v Kurodově normální formě neobsahující pravidla tvaru AB → CD generuje bezkontextové jazyky.

Penttonenova normální forma

Speciálním případem Kurodovy normální formy pro obecné frazové gramatiky (pokud v prvním pravidle výše je A = C) je Penttonenova normální forma

Jednostranná normální forma

Speciální případ Kurodovy normální formy pro kontextové gramatiky nazývá Martti Penttonen jednostranná normální forma , která obsahuje pouze pravidla následujících tvarů:

:AB → AD :A → BC :A → a

Jak napovídá jméno, pro každou kontextovou gramatiku existuje slabě ekvivalentní jednostranná (Penttonenova) normální forma.