Exercício 09.11

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

G = ({S, B, F, I}, {a}, P, S)
P = {< S >          ->  < I > < S > a a < F >  |  a a
     < S > a        ->  a a < S >
     a < S > < F >  ->  < B > a < F >  |  a
     a < B >        ->  < B > a
     < I > < B >    ->  < I > < S >
     < I > a        ->  a }

Resposta

< S >
< I > < S > a a < F >
< I > a a < S > a < F >
< I > a a a a < S > < F >
< I > a a a < B > a < F >
< I > a a < B > a a < F >
< I > a < B > a a a < F >
< I > < B > a a a a < F >
< I > < S > a a a a < F >
< I > a a < S > a a a < F >
< I > a a a a < S > a a < F >
< I > a a a a a a < S > a < F >
< I > a a a a a a a a < S > < F >
< I > a a a a a a a a
a a a a a a a a

Recomendamos