Exercício 07.49

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui accb ou cbab ou dacd como prefixo, bcad ou dcbd ou abca como subpalavra e adab ou abab ou dcab como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {a, b, c, d}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   accbcadab
                 |   accbcadcab
                 |   cbabcabab
                 |   cbabcadab
                 |   cbabcadcab
                 |   dacdcbdcab
     < pre >     ->  accb
                 |   cbab
                 |   dacd
     < presub >  ->  accbcad
                 |   cbabca
                 |   cbabcad
                 |   dacdcbd
     < sub >     ->  abca
                 |   bcad
                 |   dcbd
     < subsuf >  ->  abcabab
                 |   abcadab
                 |   bcadab
                 |   bcadcab
                 |   dcbdcab
     < suf >     ->  abab 
                 |   adab
                 |   dcab
     < alf >     ->  < alf > a
                 |   < alf > b
                 |   < alf > c
                 |   < alf > d
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {a, b, c, d}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   accbcadab
                 |   accbcadcab
                 |   cbabcabab
                 |   cbabcadab
                 |   cbabcadcab
                 |   dacdcbdcab
     < pre >     ->  accb
                 |   cbab
                 |   dacd
     < presub >  ->  accbcad
                 |   cbabca
                 |   cbabcad
                 |   dacdcbd
     < sub >     ->  abca
                 |   bcad
                 |   dcbd
     < subsuf >  ->  abcabab
                 |   abcadab
                 |   bcadab
                 |   bcadcab
                 |   dcbdcab
     < suf >     ->  abab 
                 |   adab
                 |   dcab
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Revista FOSSGIS Brasil Duolingo Um Sábado Qualquer