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.