Forma normal de Kuroda

Definição

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

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

Referências

  1. ↑ 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 
  2. ↑ 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 
  3. ↑ 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 
  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 
  5. ↑ 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