Exercício 07.45

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui bab ou dac ou ba como prefixo, abb ou cac ou acbc como subpalavra e bca ou acd ou cda 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 >
                 |   babbca
                 |   dacacd
                 |   dacacda
                 |   dacbca
                 |   dacbcda
                 |   bacbca
                 |   bacbcda
     < pre >     ->  bab
                 |   dac
                 |   ba
     < presub >  ->  babb
                 |   dacac
                 |   dacbc
                 |   bacbc
     < sub >     ->  abb
                 |   cac
                 |   acbc
     < subsuf >  ->  abbca
                 |   cacd
                 |   cacda
                 |   acbca
                 |   acbcda
     < suf >     ->  bca 
                 |   acd
                 |   cda
     < 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 >
                 |   babbca
                 |   dacacd
                 |   dacacda
                 |   dacbca
                 |   dacbcda
                 |   bacbca
                 |   bacbcda
     < pre >     ->  bab
                 |   dac
                 |   ba
     < presub >  ->  babb
                 |   dacac
                 |   dacbc
                 |   bacbc
     < sub >     ->  abb
                 |   cac
                 |   acbc
     < subsuf >  ->  abbca
                 |   cacd
                 |   cacda
                 |   acbca
                 |   acbcda
     < suf >     ->  bca 
                 |   acd
                 |   cda
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Copy Clickarvore Vida de Suporte