Exercício 08.23

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

G = ({A, B, C, D}, {x, y, z}, P, A)
P = {< A >  ->  < C > x < D >
     < B >  ->  y
            |   < A > x
     < C >  ->  z z
            |   z < A > z
     < D >  ->  y < B >
            |   < B > x }

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 = ({A, B, C, D, X1, X2, X3, Y1, Z1, Z2, Z3, Z4}, {x, y, z}, P, A)
P = {< A >  ->  < C > < X1 > < D >
     < B >  ->  y
            |   < A > < X2 >
     < C >  ->  < Z1 > < Z2 >
            |   < Z3 > < A > < Z4 >
     < D >  ->  < Y1 > < B >
            |   < B > < X3 >
     < X1 > ->  x
     < X2 > ->  x
     < X3 > ->  x
     < Y1 > ->  y
     < Z1 > ->  z
     < Z2 > ->  z
     < Z3 > ->  z
     < Z4 > ->  z }

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

G = ({A, A1, B, C, C1, D, X1, X2, X3, Y1, Z1, Z2, Z3, Z4}, {x, y, z}, P, A)
P = {< A >  ->  < C > < A1 >
     < A1 > ->  < X1 > < D >
     < B >  ->  y
            |   < A > < X2 >
     < C >  ->  < Z1 > < Z2 >
            |   < Z3 > < C1 >
     < C1 > ->  < A > < Z4 >
     < D >  ->  < Y1 > < B >
            |   < B > < X3 >
     < X1 > ->  x
     < X2 > ->  x
     < X3 > ->  x
     < Y1 > ->  y
     < Z1 > ->  z
     < Z2 > ->  z
     < Z3 > ->  z
     < Z4 > ->  z }