Exercício 07.43

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xyz ou zyx ou yzy como prefixo, xyy ou xzx ou xxz como subpalavra e yxy ou yzy ou yxx como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {x, y, z}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   zyxyyxy
                 |   zyxyyzy
                 |   zyxyyxx
     < pre >     ->  xyz
                 |   zyx
                 |   yzy
     < presub >  ->  zyxyy
                 |   zyxzx
                 |   zyxxz
     < sub >     ->  xyy
                 |   xzx
                 |   xxz
     < subsuf >  ->  xyyxy
                 |   xyyzy
                 |   xyyxx
     < suf >     ->  yxy 
                 |   yzy
                 |   yxx
     < alf >     ->  < alf > x
                 |   < alf > y
                 |   < alf > z
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {x, y, z}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   zyxyyxy
                 |   zyxyyzy
                 |   zyxyyxx
     < pre >     ->  xyz
                 |   zyx
                 |   yzy
     < presub >  ->  zyxyy
                 |   zyxzx
                 |   zyxxz
     < sub >     ->  xyy
                 |   xzx
                 |   xxz
     < subsuf >  ->  xyyxy
                 |   xyyzy
                 |   xyyxx
     < suf >     ->  yxy 
                 |   yzy
                 |   yxx
     < alf >     ->  x < alf >
                 |   y < alf >
                 |   z < alf >
                 |   ε  }

Recomendamos

Copy Kinghost Vida de Suporte