Exercício 07.48

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {x, y, z, w}, que reconheça a linguagem L = {w | w possui xzxy ou wyzy ou zyyw como prefixo, ywzy ou wxxy ou xyx como subpalavra e xwzw ou yxx ou zw 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 >
                 |   xzxywzyxx
                 |   xzxyxwzw
                 |   xzxyxx
                 |   wyzywzyxx
                 |   zyywzyxx
                 |   zyywxxyxx
     < pre >     ->  xzxy
                 |   wyzy
                 |   zyyw
     < presub >  ->  xzxywzy
                 |   xzxyx
                 |   wyzywzy
                 |   zyywzy
                 |   zyywxxy
     < sub >     ->  ywzy
                 |   wxxy
                 |   xyx
     < subsuf >  ->  ywzyxx
                 |   wxxyxx
                 |   xyxwzw
                 |   xyxx
     < suf >     ->  xwzw 
                 |   yxx
                 |   zw
     < 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 >
                 |   xzxywzyxx
                 |   xzxyxwzw
                 |   xzxyxx
                 |   wyzywzyxx
                 |   zyywzyxx
                 |   zyywxxyxx
     < pre >     ->  xzxy
                 |   wyzy
                 |   zyyw
     < presub >  ->  xzxywzy
                 |   xzxyx
                 |   wyzywzy
                 |   zyywzy
                 |   zyywxxy
     < sub >     ->  ywzy
                 |   wxxy
                 |   xyx
     < subsuf >  ->  ywzyxx
                 |   wxxyxx
                 |   xyxwzw
                 |   xyxx
     < suf >     ->  xwzw 
                 |   yxx
                 |   zw
     < alf >     ->  x < alf >
                 |   y < alf >
                 |   z < alf >
                 |   w < alf >
                 |   ε  }

Recomendamos

Revista FOSSGIS Brasil Java Magazine Vida de Programador