Kuroda normální forma - Kuroda normal form
v teorie formálního jazyka, a gramatika je v Kuroda normální forma pokud jsou všechna produkční pravidla ve tvaru:[1]
- AB → CD nebo
- A → před naším letopočtem nebo
- A → B nebo
- A → A
kde A, B, C a D jsou neterminální symboly a A je symbol terminálu.[1] Některé zdroje vynechávají A → B vzor.[2]
Je pojmenován po Sige-Yuki Kuroda, který to původně nazval a lineárně ohraničená gramatika— Terminologie, kterou poté použilo také několik dalších autorů.[3]
Každá gramatika v Kurodově normální formě je nonkontrakční, a proto generuje a kontextově citlivý jazyk. Naopak každý kontextově citlivý jazyk, který negeneruje prázdný řetězec lze generovat gramatikou v Kurodově normální formě.[2]
Jednoduchá technika přisuzovaná Györgymu Révészovi transformuje gramatiku v Kurodově podobě na Chomského CSG: AB → CD je nahrazen čtyřmi kontextově citlivými pravidly AB → AZ, AZ → WZ, WZ → WD a WD → CD. Tato technika také dokazuje, že každá nesmluvní gramatika je kontextová.[1]
Existuje podobná normální forma pro neomezené gramatiky také, který alespoň někteří autoři nazývají také „Kuroda normální forma“:[4]
- AB → CD nebo
- A → před naším letopočtem nebo
- A → A nebo
- A → ε
kde ε je prázdný řetězec. Každá neomezená gramatika je [slabě] ekvivalentní té, která používá pouze inscenace této formy.[2]
Pokud je pravidlo AB → CD z výše uvedeného vyloučeno, získá se bezkontextové jazyky.[5] The Penttonen normální forma (pro neomezené gramatiky) je zvláštní případ, kdy A = C v prvním pravidle výše.[4] U kontextově citlivých gramatik se Penttonenův normální tvar, nazývaný také jednostranný normální tvar (podle vlastní terminologie Penttonen) je jen:[1][2]
- AB → INZERÁT nebo
- A → před naším letopočtem nebo
- A → A
Jak název napovídá, pro každého kontextová gramatika, existuje [slabě] ekvivalentní jednostranný / Penttonenův normální tvar.[2]
Viz také
Reference
- ^ A b C d Masami Ito; Yuji Kobayashi; Kunitaka Shoji (2010). Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008. World Scientific. p. 182. ISBN 978-981-4317-60-3.
- ^ A b C d E Mateescu, Alexandru; Salomaa, Arto (1997). „Kapitola 4: Aspekty teorie klasického jazyka“. V Rozenberg, Grzegorz; Salomaa, Arto (eds.). Příručka formálních jazyků. Svazek I: Slovo, jazyk, gramatika. Springer-Verlag. p. 190. ISBN 978-3-540-61486-9.
- ^ Willem J. M. Levelt (2008). Úvod do teorie formálních jazyků a automatů. Nakladatelství John Benjamins. str. 126–127. ISBN 978-90-272-3250-2.
- ^ A b Alexander Meduna (2000). Automaty a jazyky: Teorie a aplikace. Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3.
- ^ Alexander Meduna (2000). Automaty a jazyky: Teorie a aplikace. Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3.
Další čtení
- Sige-Yuki Kuroda (červen 1964). "Třídy jazyků a lineárně ohraničené automaty". Informace a kontrola. 7 (2): 207–223. doi:10.1016 / S0019-9958 (64) 90120-2.
- G. Révész, „Komentář k článku„ Detekce chyb ve formálních jazycích “,„ Journal of Computer and System Sciences, sv. 8, č. 2, s. 238–242, duben 1974. doi:10.1016 / S0022-0000 (74) 80057-7 (Révészův trik)
- Penttonen, Martti (srpen 1974). „Jednostranný a oboustranný kontext ve formálních gramatikách“. Informace a kontrola. 25 (4): 371–392. doi:10.1016 / S0019-9958 (74) 91049-3.