Exercício 09.10

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

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

Resposta

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

Recomendamos