Forma Normal de Chomsky

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em ciência da computação, uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras de produção são da forma:

ou
ou

onde , e são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), é a variável inicial, e ε é a cadeia vazia. Além disso, nem nem podem ser a variável inicial.

Toda gramática na forma normal de Chomsky é uma livre de contexto, e inversamente, toda gramática livre de contexto pode ser transformada em uma equivalente que está na forma normal de Chomsky. Vários algoritmos para realizar tal transformação são conhecidos. Transformações são descritas na maioria dos livros sobre teoria dos autômatos, tais como (Hopcroft and Ullman, 1979). Como apontado por Lange and Leiß, a desvantagem destas transformações é que elas podem levar a um inchaço indesejável no tamanho da gramática. Usando para denotar o tamanho da gramática original , o tamanho do inchaço no pior dos casos pode variar de a , dependendo do algoritmo de transformação utilizado (Lange and Leiß, 2009).

Definição alternativa[editar | editar código-fonte]

Outra forma de definir a forma normal de Chomsky (Hopcroft e Ullman 1979, e Hopcroft et al. 2006) é:

Uma gramática formal está na forma reduzida de Chomsky se todas as suas regras de produção são da seguinte forma:

ou

onde , e são variáveis (símbolos não-terminais), e α é um símbolo terminal. Ao usar esta definição, ou pode ser a variável inicial.

Convertendo uma gramática para a Forma Normal de Chomsky[editar | editar código-fonte]

  1. Introduzir
  2.  : Introduzir uma nova variável inicial, e uma nova regra onde é a variável inicial anterior.
  3. Eliminar todas as regras
  4.  : Regras são regras da forma onde e onde V é a variável do alfabeto da CFG.
  5.  : Remover todas as regras com do seu lado direito (RHS, do inglês Right Hand Side - Lado da Mão Direita). Para cada regra com no seu RHS, adicione um conjunto de regras novas consistindo das diferentes combinações possíveis de substituído ou não substituído por . Se uma regra tem como um símbolo único em seu RHS, adicione uma nova regra a menos que já tenha sido removida através deste processo. Por exemplo, examine a seguinte gramática G:
  6.  ::
  7.  ::
  8.  ::
  9.  :G tem uma regra epsilon. Quando o é removido, temos o seguinte:
  10.  ::
  11.  ::
  12.  :Repare que temos que contar todas as possibilidades de e assim realmente acabamos adicionando 3 regras.
  13. Eliminar todas as regras unitárias
  14.  :
  15.  :Depois de remover todas as regras , você pode remover regras unitárias, ou regras cuja RHS contém uma variável e nenhum terminal (que é incompatível com FNC.)
  16.  :: Para remover
  17.  :: adicione a regra a menos que esta seja uma regra unitária que já foi removida.
  18. Limpar regras restantes que não estão na forma normal de Chomsky.
  19.  : Substituir por onde são novas variáveis.
  20.  : Se , substitua nas regras acima por alguma nova variável e adicione a regra .

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • John E. Hopcroft, Rajeev Motwani, e Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006. ISBN 0-321-45536-3. (See subsection 7.1.5, page 272.)
  • John E. Hopcroft e Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)
  • Michael Sipser (1997). Introduction to the Theory of Computation PWS Publishing [S.l.] ISBN 0-534-94728-X.  (Pages 98–101 of section 2.1: context-free grammars. Page 156.)
  • John Martin (2003). Introduction to Languages and the Theory of Computation McGraw Hill [S.l.] ISBN 0-07-232200-4.  (Pages 237–240 of section 6.6: simplified forms and normal forms.)
  • Michael A. Harrison (1978). Introduction to Formal Language Theory Addison-Wesley [S.l.] ISBN 978-0201029550.  (Pages 103–106.)
  • Lange, Martin e Leiß, Hans. To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm. Informatica Didactica 8, 2009. ((pdf)
  • Cole, Richard. Converting CFGs to CNF (Chomsky Normal Form), October 17, 2007. (pdf)
  • Sipser, Michael. Introduction to the Theory of Computation, 2nd edition.