Exercício 07.46

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui ab ou bcda ou bca como prefixo, dab ou acab ou cad como subpalavra e dad ou aba ou bbc 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 >
                 |   bcdaba
                 |   bcdabbc
                 |   bcdacaba
                 |   bcdacabbc
                 |   bcacaba
                 |   bcacabbc
                 |   bcadad
     < pre >     ->  ab
                 |   bcda
                 |   bca
     < presub >  ->  bcdab
                 |   bcdacab
                 |   bcacab
                 |   bcad
     < sub >     ->  dab
                 |   acab
                 |   cad
     < subsuf >  ->  daba
                 |   dabbc
                 |   acaba
                 |   acabbc
                 |   cadad
     < suf >     ->  dad 
                 |   aba
                 |   bbc
     < 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 >
                 |   bcdaba
                 |   bcdabbc
                 |   bcdacaba
                 |   bcdacabbc
                 |   bcacaba
                 |   bcacabbc
                 |   bcadad
     < pre >     ->  ab
                 |   bcda
                 |   bca
     < presub >  ->  bcdab
                 |   bcdacab
                 |   bcacab
                 |   bcad
     < sub >     ->  dab
                 |   acab
                 |   cad
     < subsuf >  ->  daba
                 |   dabbc
                 |   acaba
                 |   acabbc
                 |   cadad
     < suf >     ->  dad 
                 |   aba
                 |   bbc
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Revista LibreOffice Magazine Revista Tema Agenda TI