Exercício 09.14

Apresente uma derivação para a sentença aaabbbaaabbb sobre a gramática sensível ao contexto a seguir.

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

Resposta

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

Recomendamos

Vida de Suporte Agenda TI Vida de Programador