Exercício 07.105

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {w, x, y, z}, que reconheça a linguagem L = {w | w possui wwzx ou zwzw ou zxyw como prefixo, wzyzy ou zwxxw ou zxxwz como subpalavra e wzw ou xww ou zyx como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {w, x, y, z}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   wwzxxwzw
                 |   wwzxxwzyx
                 |   zwzwxxww
                 |   zwzwxxwzw
                 |   zwzwzyzyx
                 |   zxywzyzyx
     < pre >     ->  wwzx
                 |   zwzw
                 |   zxyw
     < presub >  ->  
                 |   wwzxxwz
                 |   zwzwxxw
                 |   zwzwzyzy
                 |   zxywzyzy
     < sub >     ->  wzyzy
                 |   zwxxw
                 |   zxxwz
     < subsuf >  ->  
                 |   wzyzyx
                 |   zwxxww
                 |   zwxxwzw
                 |   zxxwzw
                 |   zxxwzyx
     < suf >     ->  wzw 
                 |   xww
                 |   zyx
     < alf >     ->  < alf > w
                 |   < alf > x
                 |   < alf > y
                 |   < alf > z
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {w, x, y, z}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   wwzxxwzw
                 |   wwzxxwzyx
                 |   zwzwxxww
                 |   zwzwxxwzw
                 |   zwzwzyzyx
                 |   zxywzyzyx
     < pre >     ->  wwzx
                 |   zwzw
                 |   zxyw
     < presub >  ->  
                 |   wwzxxwz
                 |   zwzwxxw
                 |   zwzwzyzy
                 |   zxywzyzy
     < sub >     ->  wzyzy
                 |   zwxxw
                 |   zxxwz
     < subsuf >  ->  
                 |   wzyzyx
                 |   zwxxww
                 |   zwxxwzw
                 |   zxxwzw
                 |   zxxwzyx
     < suf >     ->  wzw 
                 |   xww
                 |   zyx
     < alf >     ->  w < alf >
                 |   x < alf >
                 |   y < alf >
                 |   z < alf >
                 |   ε  }

Recomendamos

Vida de Programador Revista Segurança Digital Revista Tema