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