Exercício 09.16

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


Resposta

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

Recomendamos

Duolingo Vida de Suporte Revista Espírito Livre