Forma Normal de Chomsky

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:

${\displaystyle A\rightarrow BC}$ ou

${\displaystyle A\rightarrow \alpha }$ ou

${\displaystyle S\rightarrow \varepsilon }$

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

Definição alternativa

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:

${\displaystyle A\rightarrow \,BC}$ ou

${\displaystyle A\rightarrow \,\alpha }$

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

Convertendo uma gramática para a Forma Normal de Chomsky

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

Ver também

• Forma normal de Greibach
• Algoritmo CYK

Referências

• 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. [S.l.]: PWS Publishing. 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. [S.l.]: McGraw Hill. 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. [S.l.]: Addison-Wesley. 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.