Exercício 07.40
Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xxy ou yyz como prefixo, yxz ou yzx como subpalavra e xzz ou xyx como sufixo}.
Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {x, y, z}, que reconheça a linguagem L = {w | w possui xxy ou yyz como prefixo, yxz ou yzx como subpalavra e xzz ou xyx como sufixo}.
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 >
| xxyxzz
| xxyzxyx
| xxyzxzz
| yyzxyx
| yyzxzz
< pre > -> xxy
| yyz
< presub > -> xxyxz
| xxyzx
| yyzx
< sub > -> yxz
| yzx
< subsuf > -> yxzz
| yzxyx
| yzxzz
< suf > -> xyx
| xzz
< alf > -> < alf > x
| < alf > y
| < alf > z
| ε }
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 >
| xxyxzz
| xxyzxyx
| xxyzxzz
| yyzxyx
| yyzxzz
< pre > -> xxy
| yyz
< presub > -> xxyxz
| xxyzx
| yyzx
< sub > -> yxz
| yzx
< subsuf > -> yxzz
| yzxyx
| yzxzz
< suf > -> xyx
| xzz
< alf > -> x < alf >
| y < alf >
| z < alf >
| ε }