Exercício 09.04

Apresente uma derivação para a sentença aabbbccddd sobre a gramática a seguir.

G = ({S, A, B, X, Y}, {a, b, c, d}, P, S)
P = {< S >        ->  < A > < B > 
     < A >        ->  a < A > < X > | a < X >
     < B >        ->  b < B > d | b < Y > d
     < X > b      ->  b < X >
     < X > < Y >  ->  < Y > c
     < Y >        ->  ε }

Resposta

< S >
< A > < B >
a < A > < X > < B >
a a < X > < X > < B >
a a < X > < X > b < B > d
a a < X > < X > b b < B > d d
a a < X > < X > b b b < Y > d d d
a a < X > b < X > b b < Y > d d d
a a b < X > < X > b b < Y > d d d
a a b < X > b < X > b < Y > d d d
a a b b < X > < X > b < Y > d d d
a a b b < X > b < X > < Y > d d d
a a b b b < X > < X > < Y > d d d
a a b b b < X > < Y > c d d d
a a b b b < Y > c c d d d
a a b b b c c d d d

Recomendamos