Forma normal de Kuroda
 | Foram assinalados vários problemas nesta página ou se(c)ção: |
Definição[editar | editar código-fonte]
Na linguagem formal, a gramática está na forma normal de Kuroda se todas as produções são da forma:[1]
AB → CD ou A → BC ou A → B ou A → α
Onde A,B,C e D são símbolos não terminais e α um síbolo terminal.[1] Alguns autores omitem a terceira cláusula (A → B).[2] Foi nomeado assim em homenagem a Sige-Yuki Kuroda, o qual originalmente chamava de gramática linearmente limitada—terminologia ainda utilizada por muitos autores.[3] Toda gramática na forma normal de Kuroda está na forma não contraída e portanto é possível gerar uma linguagem sensível ao contexto. Reciprocamente, toda linguagem sensível ao contexto, a qual não gere uma cadeia vazia, pode ser gerada por uma gramática na forma normal de Koruda.[2]
Uma técnica genuínamente atribuída a György Révész transforma a gramática na forma normal de Koruda para a forma normal de Chomsky AB → CD é substituída por quatro regras sensíveis ao contexto AB → AZ, AZ → WZ, WZ → WD e WD → CD. Esta técnica também prova que qualquer gramática na sua forma não contráida, é sensível ao contexto.[1]
Existe uma forma normal similar para gramática irrestrita, que alguns autores também a nomeia como forma normal de Kuroda.[4]
AB → CD ou A → BC ou A → a ou A → ε
Onde ε é uma string vazia. Toda gramática irrestrita é (fracamente) equivalente as gramáticas utilizando apenas produções dessa forma.[2] Se a regra AB → CD for eliminada, como no exemplo abaixo, então são obtidas linguagens livres de contexto.[5]
Forma normal de Penttonen[editar | editar código-fonte]
A forma normal de Penttonen (para gramática irrestrita) é um caso especial onde A = C na primeira regra abaixo.[4] Para gramáticas sensíveis ao contexto, a forma normal de Penttonen é como segue:[1][2]
AB → AD ou A → BC ou A → a
Para cada gramática sensível ao contexto, existe [fracamente] uma forma normal de Penttonen.[2]
Ver Também[editar | editar código-fonte]
Referências
- ↑ a b c d Masami Ito; Yūji Kobayashi; Kunitaka Shoji (2010). Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008. [S.l.]: World Scientific. p. 182. ISBN 978-981-4317-60-3
- ↑ a b c d e Mateescu, Alexandru; Salomaa, Arto (1997). «Chapter 4: Aspects of Classical Language Theory». In: Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. [S.l.]: Springer-Verlag. p. 190. ISBN 3-540-61486-9
- ↑ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. [S.l.]: John Benjamins Publishing. pp. 126–127. ISBN 90-272-3250-4
- ↑ a b Alexander Meduna (2000). Automata and Languages: Theory and Applications. [S.l.]: Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3
- ↑ Alexander Meduna (2000). Automata and Languages: Theory and Applications. [S.l.]: Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3
Leituras adicional[editar | editar código-fonte]
- Sige-Yuki Kuroda (junho de 1964). «Classes of languages and linear-bounded automata» (PDF). Information and Control. 7 (2): 207–223. doi:10.1016/S0019-9958(64)90120-2
- G. Révész, “Comment on the paper ‘Error detection in formal languages,’” Journal of Computer and System Sciences, vol. 8, no. 2, pp. 238–242, Apr. 1974. doi:10.1016/S0022-0000(74)80057-7 (Révész' trick)
- Penttonen, Martti (agosto de 1974). «One-sided and two-sided context in formal grammars» (PDF). Information and Control. 25 (4): 371–392. doi:10.1016/S0019-9958(74)91049-3