Exercício 07.90

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui wxy ou xyy ou zwx como prefixo, xyz ou xzw ou ywz como subpalavra e wxz ou yzy ou zyw como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {x, y, z, w}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   wxywzyw
                 |   wxyzy
                 |   wxyzyw
                 |   xyywzyw
                 |   zwxyzy
                 |   zwxyzyw
                 |   zwxzwxz
     < pre >     ->  wxy
                 |   xyy
                 |   zwx
     < presub >  ->  wxywz
                 |   wxyz
                 |   xyywz
                 |   zwxyz
                 |   zwxzw
     < sub >     ->  xyz
                 |   xzw
                 |   ywz
     < subsuf >  ->  xyzy
                 |   xyzyw
                 |   xzwxz
                 |   ywzyw
     < suf >     ->  wxz 
                 |   yzy
                 |   zyw
     < alf >     ->  < alf > x
                 |   < alf > y
                 |   < alf > z
                 |   < alf > w
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {x, y, z, w}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   wxywzyw
                 |   wxyzy
                 |   wxyzyw
                 |   xyywzyw
                 |   zwxyzy
                 |   zwxyzyw
                 |   zwxzwxz
     < pre >     ->  wxy
                 |   xyy
                 |   zwx
     < presub >  ->  wxywz
                 |   wxyz
                 |   xyywz
                 |   zwxyz
                 |   zwxzw
     < sub >     ->  xyz
                 |   xzw
                 |   ywz
     < subsuf >  ->  xyzy
                 |   xyzyw
                 |   xzwxz
                 |   ywzyw
     < suf >     ->  wxz 
                 |   yzy
                 |   zyw
     < alf >     ->  x < alf >
                 |   y < alf >
                 |   z < alf >
                 |   w < alf >
                 |   ε  }

Recomendamos

cert.br Kinghost Vida de Programador