Exercício 07.51

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abcd ou dcba ou baba como prefixo, badcd ou abcbc ou ccdab como subpalavra e bcca ou cdac ou dabc 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 >
                 |   dcbadcdac
                 |   dcbadcdabc
                 |   dcbabcbcca
                 |   dcbabcbcdac
                 |   babadcdac
                 |   babadcdabc
                 |   bababcbcca
                 |   bababcbcdac
     < pre >     ->  abcd
                 |   dcba
                 |   baba
     < presub >  ->  dcbadcd
                 |   dcbabcbc
                 |   babadcd
                 |   bababcbc
     < sub >     ->  badcd
                 |   abcbc
                 |   ccdab
     < subsuf >  ->  badcdac
                 |   badcdabc
                 |   abcbcca
                 |   abcbcdac
                 |   ccdabcca
                 |   ccdabc
     < suf >     ->  bcca 
                 |   cdac
                 |   dabc
     < 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 >
                 |   dcbadcdac
                 |   dcbadcdabc
                 |   dcbabcbcca
                 |   dcbabcbcdac
                 |   babadcdac
                 |   babadcdabc
                 |   bababcbcca
                 |   bababcbcdac
     < pre >     ->  abcd
                 |   dcba
                 |   baba
     < presub >  ->  dcbadcd
                 |   dcbabcbc
                 |   babadcd
                 |   bababcbc
     < sub >     ->  badcd
                 |   abcbc
                 |   ccdab
     < subsuf >  ->  badcdac
                 |   badcdabc
                 |   abcbcca
                 |   abcbcdac
                 |   ccdabcca
                 |   ccdabc
     < suf >     ->  bcca 
                 |   cdac
                 |   dabc
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Agenda TI Revista Digital Kinghost