Exercício 09.17

Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui cbc como prefixo, cba como subpalavra e bab como sufixo}.


Resposta

G = ({A, B, C, D, E, F, G, H, I, J}, {a, b, c}, P, A)
P = {< A >  ->  < B > b
     < B >  ->  < C > a
     < C >  ->  < D > b  |  < F > b
     < D >  ->  < D > a  |  < D > b  |  < D > c  |  < E > a
     < E >  ->  < F > b
     < F >  ->  < G > c  |  < H > c
     < G >  ->  < G > a  |  < G > b  |  < G > c  |  < H > c
     < H >  ->  < I > b
     < I >  ->  < J > c
     < J >  ->  ε }

Recomendamos

Vida de Programador Revista FOSSGIS Brasil Um Sábado Qualquer