Exercício 07.53

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


Resposta com recursividade à esquerda

G = ({prg, exp1, exp2, pre, subsuf1, subsuf2, suf1, suf2, alf}, {a, b, c}, P, prg)
P = {< prg >     ->  < exp1 >
                 |   < exp2 >
     < exp1 >    ->  < pre > < alf > abb < alf > < suf1 >
                 |   cbabb < alf > < suf1 >
                 |   < pre > < alf > < subsuf1 >
                 |   cbabbab
                 |   cbabbcb
     < exp2 >    ->  < pre > < alf > acc < alf > < suf2 >
                 |   cbacc < alf > < suf2 >
                 |   < pre > < alf > < subsuf2 >
                 |   cbaccaa
                 |   cbaccbb
     < pre >     ->  abc
                 |   cba
     < subsuf1 > ->  abbab
                 |   abbcb
     < subsuf2 > ->  accaa
                 |   accbb
     < suf1 >    ->  bab
                 |   bcb
     < suf2 >    ->  caa
                 |   cbb
     < alf >     ->  < alf > a
                 |   < alf > b
                 |   < alf > c
                 |   ε  }

Resposta com recursividade à direita

G = ({prg, exp1, exp2, pre, subsuf1, subsuf2, suf1, suf2, alf}, {a, b, c}, P, prg)
P = {< prg >     ->  < exp1 >
                 |   < exp2 >
     < exp1 >    ->  < pre > < alf > abb < alf > < suf1 >
                 |   cbabb < alf > < suf1 >
                 |   < pre > < alf > < subsuf1 >
                 |   cbabbab
                 |   cbabbcb
     < exp2 >    ->  < pre > < alf > acc < alf > < suf2 >
                 |   cbacc < alf > < suf2 >
                 |   < pre > < alf > < subsuf2 >
                 |   cbaccaa
                 |   cbaccbb
     < pre >     ->  abc
                 |   cba
     < subsuf1 > ->  abbab
                 |   abbcb
     < subsuf2 > ->  accaa
                 |   accbb
     < suf1 >    ->  bab
                 |   bcb
     < suf2 >    ->  caa
                 |   cbb
     < alf >     ->  a < alf >
                 |   b < alf >
                 |   c< alf >
                 |   ε  }

Recomendamos

Java Magazine cert.br Revista Digital