Exercício 07.44

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abc ou bcd ou cdd como prefixo, dba ou cda ou cab como subpalavra e adb ou dad ou bca 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 >
                 |   bcdbadb
                 |   cddbadb
                 |   abcdadb
                 |   abcdad
                 |   bcdadb
                 |   bcdad
                 |   abcabca
     < pre >     ->  abc
                 |   bcd
                 |   cdd
     < presub >  ->  abcda
                 |   abcab
                 |   bcdba
                 |   bcda
                 |   cddba
     < sub >     ->  dba
                 |   cda
                 |   cab
     < subsuf >  ->  dbadb
                 |   cdadb
                 |   cdad
                 |   cabca
     < suf >     ->  adb 
                 |   dad
                 |   bca
     < 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 >
                 |   bcdbadb
                 |   cddbadb
                 |   abcdadb
                 |   abcdad
                 |   bcdadb
                 |   bcdad
                 |   abcabca
     < pre >     ->  abc
                 |   bcd
                 |   cdd
     < presub >  ->  abcda
                 |   abcab
                 |   bcdba
                 |   bcda
                 |   cddba
     < sub >     ->  dba
                 |   cda
                 |   cab
     < subsuf >  ->  dbadb
                 |   cdadb
                 |   cdad
                 |   cabca
     < suf >     ->  adb 
                 |   dad
                 |   bca
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Revista FOSSGIS Brasil Revista Digital Agenda TI