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:

A \rightarrow BC ou
A \rightarrow \alpha ou
S \rightarrow \varepsilon

onde A, B e C são variáveis (símbolos não-terminais), α é um símbolo terminal (um símbolo que representa um valor constante), S é a variável inicial, e ε é a cadeia vazia. Além disso, nem B nem C 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 |G| para denotar o tamanho da gramática original G, o tamanho do inchaço no pior dos casos pode variar de |G|^2 a 2^{2 |G|}, 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:

A \rightarrow\, BC ou
A \rightarrow\, \alpha

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

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

  1. Introduzir S_0
  2.  : Introduzir uma nova variável inicial, S_0 e uma nova regra S_0 \rightarrow S onde S é a variável inicial anterior.
  3. Eliminar todas as regras \epsilon
  4.  : Regras \epsilon são regras da forma A \rightarrow \epsilon onde A \not= S_0 e A \in V onde V é a variável do alfabeto da CFG.
  5.  : Remover todas as regras com \epsilon do seu lado direito (RHS, do inglês Right Hand Side - Lado da Mão Direita). Para cada regra com A no seu RHS, adicione um conjunto de regras novas consistindo das diferentes combinações possíveis de A substituído ou não substituído por \epsilon. Se uma regra tem A como um símbolo único em seu RHS, adicione uma nova regra R = A \rightarrow \epsilon a menos que R já tenha sido removida através deste processo. Por exemplo, examine a seguinte gramática G:
  6.  :: S \rightarrow AbA | B
  7.  :: B \rightarrow b | c
  8.  :: A \rightarrow \epsilon
  9.  :G tem uma regra epsilon. Quando o A \rightarrow \epsilon é removido, temos o seguinte:
  10.  :: S \rightarrow AbA | Ab | bA | b | B
  11.  :: B \rightarrow b | c
  12.  :Repare que temos que contar todas as possibilidades de A \rightarrow \epsilon e assim realmente acabamos adicionando 3 regras.
  13. Eliminar todas as regras unitárias
  14.  :A \rightarrow B \ni A,B \in V
  15.  :Depois de remover todas as regras \epsilon, 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 A \rightarrow B
  17.  :: \forall B \rightarrow U adicione a regra A \rightarrow U 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 A \rightarrow u_1,u_2, ... u_k, k \ge 3, u_1 \in V \cup \Sigma por A \rightarrow u_1 A_1 , A_1 \rightarrow u_2 A_2 , ... , A_{k-2} \rightarrow u_{k-1} u_k onde A_i são novas variáveis.
  20.  : Se u_i \in \Sigma, substitua u_i nas regras acima por alguma nova variável v_i e adicione a regra v_i \rightarrow u_i.

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. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. ISBN 0-534-94728-X (Pages 98–101 of section 2.1: context-free grammars. Page 156.)
  • John Martin. Introduction to Languages and the Theory of Computation. [S.l.]: McGraw Hill, 2003. ISBN 0-07-232200-4 (Pages 237–240 of section 6.6: simplified forms and normal forms.)
  • Michael A. Harrison. Introduction to Formal Language Theory. [S.l.]: Addison-Wesley, 1978. 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.