Exercício 07.39

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c}, que reconheça a linguagem L = {w | w possui bbc ou acc como prefixo, cab ou bcb como subpalavra e bba ou abc como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {a, b, c}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   accabc
                 |   accabba
                 |   bbcabc
                 |   bbcbba
                 |   bbcabba
     < pre >     ->  acc
                 |   bbc
     < presub >  ->  accab
                 |   bbcb
                 |   bbcab
     < sub >     ->  bcb
                 |   cab
     < subsuf >  ->  bcbba
                 |   cabc
                 |   cabba
     < suf >     ->  abc 
                 |   bba
     < alf >     ->  < alf > a
                 |   < alf > b
                 |   < alf > c
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {a, b, c}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   accabc
                 |   accabba
                 |   bbcabc
                 |   bbcbba
                 |   bbcabba
     < pre >     ->  acc
                 |   bbc
     < presub >  ->  accab
                 |   bbcb
                 |   bbcab
     < sub >     ->  bcb
                 |   cab
     < subsuf >  ->  bcbba
                 |   cabc
                 |   cabba
     < suf >     ->  abc 
                 |   bba
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   ε  }

Recomendamos

Kinghost Revista Digital Agenda TI