Forma normal de Chomsky
Um CFG está na forma normal de Chomsky se as produções estiverem nas seguintes formas -
- A → a
- A → BC
- S → ε
onde A, B e C são não terminais e a é terminal.
Algoritmo para converter na forma normal de Chomsky -
Step 1 - Se o símbolo de início S ocorre em algum lado direito, crie um novo símbolo de início S’ e uma nova produção S’→ S.
Step 2- Remova produções nulas. (Usando o algoritmo de remoção de produção nula discutido anteriormente)
Step 3- Remova produções unitárias. (Usando o algoritmo de remoção de produção da unidade discutido anteriormente)
Step 4 - Substitua cada produção A → B1…Bn Onde n > 2 com A → B1C Onde C → B2 …Bn. Repita esta etapa para todas as produções com dois ou mais símbolos no lado direito.
Step 5 - Se o lado direito de qualquer produção estiver na forma A → aB onde a é um terminal e A, B são não terminais, então a produção é substituída por A → XB e X → a. Repita esta etapa para cada produção que está no formulárioA → aB.
Problema
Converta o seguinte CFG em CNF
S → ASA | aB, A → B | S, B → b | ε
Solução
(1) Desde a S aparece no RHS, adicionamos um novo estado S0 e S0→S é adicionado ao conjunto de produção e se torna -
S 0 → S, S → ASA | aB, A → B | S, B → b | ∈
(2) Agora vamos remover as produções nulas -
B → ∈ e A → ∈
Depois de remover B → ε, o conjunto de produção torna-se -
S 0 → S, S → ASA | aB | a, A → B | S | ∈, B → b
Depois de remover A → ∈, o conjunto de produção se torna -
S 0 → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b
(3) Agora vamos remover as produções unitárias.
Depois de remover S → S, o conjunto de produção se torna -
S 0 → S, S → ASA | aB | a | AS | SA, A → B | S, B → b
Depois de remover S 0 → S, o conjunto de produção torna-se -
S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA
A → B | S, B → b
Depois de remover A → B, o conjunto de produção se torna -
S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA
A → S | b
B → b
Depois de remover A → S, o conjunto de produção se torna -
S 0 → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA
A → b | ASA | aB | a | AS | SA, B → b
(4) Agora vamos descobrir mais de duas variáveis no RHS
Aqui, S 0 → ASA, S → ASA, A → ASA viola dois não terminais em RHS
Portanto, aplicaremos as etapas 4 e 5 para obter o seguinte conjunto de produção final que está em CNF -
S 0 → AX | aB | a | AS | SA
S → AX | aB | a | AS | SA
A → b | AX | aB | a | AS | SA
B → b
X → SA
(5)Temos que mudar as produções S 0 → aB, S → aB, A → aB
E o conjunto de produção final se torna -
S 0 → AX | YB | a | AS | SA
S → AX | YB | a | AS | SA
A → b A → b | AX | YB | a | AS | SA
B → b
X → SA
S → a