Exercício 07.50

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui abab ou acdb ou bbac como prefixo, accba ou abccb ou badad como subpalavra e adc ou bab ou cbb 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 >
                 |   ababccbab
                 |   ababccbb
                 |   ababadadc
                 |   acdbadadc
                 |   bbaccbadc
                 |   bbaccbab
     < pre >     ->  abab
                 |   acdb
                 |   bbac
     < presub >  ->  ababccb
                 |   ababadad
                 |   acdbadad
                 |   bbaccba
     < sub >     ->  accba 
                 |   abccb
                 |   badad
     < subsuf >  ->  accbadc
                 |   accbab
                 |   abccbab
                 |   abccbb
                 |   badadc
     < suf >     ->  adc 
                 |   bab
                 |   cbb
     < 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 >
                 |   ababccbab
                 |   ababccbb
                 |   ababadadc
                 |   acdbadadc
                 |   bbaccbadc
                 |   bbaccbab
     < pre >     ->  abab
                 |   acdb
                 |   bbac
     < presub >  ->  ababccb
                 |   ababadad
                 |   acdbadad
                 |   bbaccba
     < sub >     ->  accba 
                 |   abccb
                 |   badad
     < subsuf >  ->  accbadc
                 |   accbab
                 |   abccbab
                 |   abccbb
                 |   badadc
     < suf >     ->  adc 
                 |   bab
                 |   cbb
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c < alf >
                 |   d < alf >
                 |   ε  }

Recomendamos

Revista LibreOffice Magazine Revista Digital Kinghost