Exercício 07.47

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iik ou kji ou jkj como prefixo, kjji ou jiik ou ikki como subpalavra e ikk ou jii ou kkj como sufixo}.


Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {i, j, k}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   iikjjikk
                 |   iikjjii
                 |   iikkikk
                 |   kjiikk
                 |   kjiikkj
                 |   kjikkikk
                 |   jkjjikk
                 |   jkjjii
                 |   jkjiikk
                 |   jkjiikkj
     < pre >     ->  iik
                 |   kji
                 |   jkj
     < presub >  ->  iikjji
                 |   iikki
                 |   kjiik
                 |   kjikki
                 |   jkjji
                 |   jkjiik
     < sub >     ->  kjji
                 |   jiik
                 |   ikki
     < subsuf >  ->  kjjikk
                 |   kjjii
                 |   jiikk
                 |   jiikkj
                 |   ikkikk
     < suf >     ->  ikk 
                 |   jii
                 |   kkj
     < alf >     ->  < alf > i
                 |   < alf > j
                 |   < alf > k
                 |   ε  }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {i, j, k}, P, exp)
P = {< exp >     ->  < pre > < alf > < sub > < alf > < suf >
                 |   < presub > < alf > < suf >
                 |   < pre > < alf > < subsuf >
                 |   iikjjikk
                 |   iikjjii
                 |   iikkikk
                 |   kjiikk
                 |   kjiikkj
                 |   kjikkikk
                 |   jkjjikk
                 |   jkjjii
                 |   jkjiikk
                 |   jkjiikkj
     < pre >     ->  iik
                 |   kji
                 |   jkj
     < presub >  ->  iikjji
                 |   iikki
                 |   kjiik
                 |   kjikki
                 |   jkjji
                 |   jkjiik
     < sub >     ->  kjji
                 |   jiik
                 |   ikki
     < subsuf >  ->  kjjikk
                 |   kjjii
                 |   jiikk
                 |   jiikkj
                 |   ikkikk
     < suf >     ->  ikk 
                 |   jii
                 |   kkj
     < alf >     ->  i < alf >
                 |   j < alf >
                 |   k < alf >
                 |   ε  }

Recomendamos

Revista Segurança Digital Clique Alimentos Copy