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

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

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, B, A1, A2, A3, B1, B2, B3}, {a, b}, P, S)
P = {< S >  ->  < B1 > < A >
            |   < A1 > < B >
     < A >  ->  < B2 > < A > < A >
            |   < A2 > < S >
            |   a
     < B >  ->  < A3 > < B > < B >
            |   < B3 > < S >
            |   b
     < A1 > ->  a
     < A2 > ->  a
     < A3 > ->  a
     < B1 > ->  b
     < B2 > ->  b
     < B3 > ->  b }

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

G = ({S, A, B, A1, A2, A3, B1, B2, B3, X, Y}, {a, b}, P, S)
P = {< S >  ->  < B1 > < A >
            |   < A1 > < B >
     < A >  ->  < B2 > < X >
            |   < A2 > < S >
            |   a
     < X >  ->  < A > < A >
     < B >  ->  < A3 > < Y >
            |   < B3 > < S >
            |   b
     < Y >  ->  < B > < B >
     < A1 > ->  a
     < A2 > ->  a
     < A3 > ->  a
     < B1 > ->  b
     < B2 > ->  b
     < B3 > ->  b }