Kurodova normální forma
Kurodova normální forma je tvar formální gramatiky, ve které jsou všechna odvozovací pravidla tvaru:[1]
- AB → CD
- A → BC
- A → B
- A → a
- A → BC
kde A, B, C a D jsou neterminální symboly, a je terminální symbol[1]. Někteří autoři nepřipouštějí pravidla tvaru A → B[2].
Pro gramatiky tohoto tvaru používal Sige-Yuki Kuroda a několik dalších autorů původně název lineární omezená gramatika (anglicky linear bounded grammar).[3]
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ě[2]
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á.[1]
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“:[4]
- AB → CD
- A → BC
- A → a
- A → ε
- A → BC
kde ε je prázdný řetězec. Každá obecná frazová gramatika je slabě ekvivalentní s gramatikou tohoto tvaru[2].
Kurodova normální forma pro bezkontextové gramatiky
Gramatika v Kurodově normální formě neobsahující pravidla tvaru AB → CD generuje bezkontextové jazyky.[5]
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[4]
Jednostranná normální forma
Speciální případ Kurodovy normální formy pro kontextové gramatiky nazývá Martti Penttonen jednostranná normální forma (anglicky one-sided normal form), která obsahuje pouze pravidla následujících tvarů:[1][2]
- AB → AD
- A → BC
- A → a
- A → BC
Jak napovídá jméno, pro každou kontextovou gramatiku existuje slabě ekvivalentní jednostranná (Penttonenova) normální forma[2].
Odkazy
Reference
V tomto článku byl použit překlad textu z článku Kuroda normal form na anglické Wikipedii.
- ↑ a b c d Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008. [s.l.]: World Scientific, 2010. Dostupné online. ISBN 978-981-4317-60-3.
- ↑ a b c d e MATEESCU, Alexandru; SALOMAA, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. [s.l.]: Springer-Verlag, 1997. ISBN 3-540-61486-9. Kapitola 4: Aspects of Classical Language Theory.
- ↑ Willem J. M. Levelt. An Introduction to the Theory of Formal Languages and Automata. [s.l.]: John Benjamins Publishing, 2008. Dostupné online. ISBN 90-272-3250-4.
- ↑ a b Alexander Meduna. Automata and Languages: Theory and Applications. [s.l.]: Springer Science & Business Media, 2000. Dostupné online. ISBN 978-1-85233-074-3.
- ↑ Alexander Meduna. Automata and Languages: Theory and Applications. [s.l.]: Springer Science & Business Media, 2000. Dostupné online. ISBN 978-1-85233-074-3.
Literatura
- Sige-Yuki Kuroda. Classes of languages and linear-bounded automata. Information and Control. Červen 1964, čís. 2. Dostupné online. DOI 10.1016/S0019-9958(64)90120-2.
- RÉVÉSZ, György. Comment on the Paper “Error detection in formal languages”. Journal of Computer and System Sciences. Duben 1974, čís. 2. Dostupné online. DOI 10.1016/S0022-0000(74)80057-7. (Révészův trik)
- PENTTONEN, Martti. One-sided and two-sided context in formal grammars. Information and Control. Aug 1974. Dostupné online. DOI 10.1016/S0019-9958(74)91049-3.