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.
Odkazy
Reference
Literatura
(Révészův trik)
Související články Backusova–Naurova forma Chomského normální forma Greibachové normální forma
Kategorie:Formální jazyky