CNF significa forma normal de Chomsky. Uma CFG (gramática livre de contexto) está em CNF (forma normal de Chomsky) se todas as regras de produção satisfizerem uma das seguintes condições:

• Comece a gerar o símbolo ε. Por exemplo, A → ε.
• Um não-terminal gerando dois não-terminais. Por exemplo, S → AB.
• Um não terminal gerando um terminal. Por exemplo, S → uma.

Por exemplo:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

As regras de produção da Gramática G1 satisfazem as regras especificadas para CNF, portanto a gramática G1 está em CNF. No entanto, a regra de produção da Gramática G2 não satisfaz as regras especificadas para CNF, pois S → aZ contém terminal seguido de não-terminal. Portanto a gramática G2 não está na CNF.

expressões lambda java

Passos para converter CFG em CNF

Passo 1: Elimine o símbolo inicial do RHS. Se o símbolo inicial T estiver no lado direito de qualquer produção, crie uma nova produção como:

 S1 → S 

Onde S1 é o novo símbolo inicial.

Passo 2: Na gramática, retire as produções nulas, unitárias e inúteis. Você pode consultar a Simplificação do CFG.

tempróximo java

Etapa 3: Eliminar terminais do RHS da produção caso existam com outros não terminais ou terminais. Por exemplo, a produção S → aA pode ser decomposta como:

 S → RA R → a 

Passo 4: Elimine RHS com mais de dois não terminais. Por exemplo, S → ASB pode ser decomposto como:

 S → RS R → AS 

Exemplo:

Converta o CFG fornecido em CNF. Considere a gramática dada G1:

 S → a | aA | B A → aBB | ε B → Aa | b 

Solução:

Passo 1: Criaremos uma nova produção S1 → S, pois o símbolo inicial S aparece no RHS. A gramática será:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Passo 2: Como a gramática G1 contém produção nula de A → ε, sua remoção da gramática resulta:

string.substring java

 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Agora, como a gramática G1 contém produção unitária S → B, seu rendimento de remoção:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

Remova também a produção unitária S1 → S, sua remoção da gramática resulta:

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Etapa 3: Na regra de produção S0 → aA | Aa, S → aA | Aa, A → aBB e B → Aa, o terminal a existe no RHS com não terminais. Portanto, substituiremos o terminal a por X:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Passo 4: Na regra de produção A → XBB, RHS possui mais de dois símbolos, retirando-o do rendimento gramatical:

tipos de dados em java

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Portanto, para a gramática dada, este é o CNF necessário.