Definição

Na linguagem formal, a gramática está na forma normal de Kuroda se todas as produções são da forma:

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. Alguns autores omitem a terceira cláusula (A → B). Foi nomeado assim em homenagem a Sige-Yuki Kuroda, o qual originalmente chamava de gramática linearmente limitada—terminologia ainda utilizada por muitos autores. 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.

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.

Existe uma forma normal similar para gramática irrestrita, que alguns autores também a nomeia como forma normal de Kuroda.

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. Se a regra AB → CD for eliminada, como no exemplo abaixo, então são obtidas linguagens livres de contexto.

Forma normal de Penttonen

A forma normal de Penttonen (para gramática irrestrita) é um caso especial onde A = C na primeira regra abaixo. Para gramáticas sensíveis ao contexto, a forma normal de Penttonen é como segue:

AB → AD ou A → BC ou A → a

Para cada gramática sensível ao contexto, existe [fracamente] uma forma normal de Penttonen.

Ver também

Formalismo de Backus-Naur Forma normal de Chomsky Forma normal de Greibach

Leituras adicional

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. (Révész' trick)

Categoria:Linguagens formais