Exercício 09.09

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

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

Resposta

< S >
a < A > b b a
a a b b b < A > b a
a a b b b b < A > a
a a b b b < B > b a a
a a b b < B > b b a a
a a b < B > b b b a a
a a < B > b b b b a a
a a < A > b b b b a a
a a a b b b < A > b b b a a
a a a b b b b < A > b b a a
a a a b b b b b < A > b a a
a a a b b b b b b < A > a a
a a a b b b b b < B > b a a a
a a a b b b b < B > b b a a a
a a a b b b < B > b b b a a a
a a a b b < B > b b b b a a a
a a a b < B > b b b b b a a a
a a a < B > b b b b b b a a a
a a a < A > b b b b b b a a a
a a a b b b b b b a a a