Exercício 08.40

Converta para a Forma Normal de Chomsky a gramática:

G = ({S, A, B, C}, {a, b, c}, P, S)
P = {< S >  ->  < A > < B > < C >
            |   < C > < B > < A >
     < A >  ->  a
     < B >  ->  < B > a < C >
            |   < A > < C > c
     < C >  ->  a < B >
            |   b }

Resposta

1. Simplificação da gramática livre do contexto

A gramática livre do contexto está simplificada.

2. Conversão das produções contendo terminais para a forma < A > -> a

G = ({S, A, A₁, A₂, B, C, C₁}, {a, b, c}, P, S)
P = {< S >  ->  < A > < B > < C >
            |   < C > < B > < A >
     < A >  ->  a
     < A₁ >  ->  a
     < A₂ >  ->  a
     < B >  ->  < B > < A₁ > < C >
            |   < A > < C > < C₁ >
     < C >  ->  < A₂ > < B >
            |   b
     < C₁ >  ->  c }

3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >

G = ({S, S₁, S₂, A, A₁, A₂, B, B₁, B₂, C, C₁}, {a, b, c}, P, S)
P = {< S >  ->  < A > < S₁ >
            |   < C > < S₂ >
     < S₁ > ->  < B > < C >
     < S₂ > ->  < B > < A >
     < A >  ->  a
     < A₁ > ->  a
     < A₂ > ->  a
     < B >  ->  < B > < B₁ >
            |   < A > < B₂ >
     < B₁ > ->  < A₁ > < C >
     < B₂ > ->  < C > < C₁ >
     < C >  ->  < A₂ > < B >
            |   b
     < C₁ > ->  c }