Tutoriais - Linguagens Formais e Autômatos
Tutoriais
Linguagens Formais e Autômatos

1. Ybadoo
2. Tutoriais
3. Linguagens Formais e Autômatos
4. Gramáticas Livre do Contexto (GLC)
5. Exercício 07.121

Exercício 07.121

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 124 ou 323 ou 432 como prefixo, 233 ou 2434 ou 424 como subpalavra e 241 ou 342 ou 412 como sufixo}.

Solução do Exercício

Resposta com recursividade à esquerda

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {1, 2, 3, 4}, P, exp)
P = {<exp> ::= <pre> <alf> <sub> <alf> <suf>
            |  <presub> <alf> <suf>
            |  <pre> <alf> <subsuf>
            |  124241
            |  1242412
            |  1243412
            |  124342
            |  323342
            |  4323342
            |  43243412
            |  4324342
     <pre> ::= 124
            |  323
            |  432
     <presub> ::= 12424
               |  12434
               |  3233
               |  43233
               |  432434
     <sub> ::= 233
            |  2434
            |  424
     <subsuf> ::= 23342
               |  243412
               |  24342
               |  4241
               |  42412
     <suf> ::= 241
            |  342
            |  412
     <alf> ::= <alf> 1
            |  <alf> 2
            |  <alf> 3
            |  <alf> 4
            |  ε }

Resposta com recursividade à direita

G = ({exp, pre, presub, sub, subsuf, suf, alf}, {1, 2, 3, 4}, P, exp)
P = {<exp> ::= <pre> <alf> <sub> <alf> <suf>
            |  <presub> <alf> <suf>
            |  <pre> <alf> <subsuf>
            |  124241
            |  1242412
            |  1243412
            |  124342
            |  323342
            |  4323342
            |  43243412
            |  4324342
     <pre> ::= 124
            |  323
            |  432
     <presub> ::= 12424
               |  12434
               |  3233
               |  43233
               |  432434
     <sub> ::= 233
            |  2434
            |  424
     <subsuf> ::= 23342
               |  243412
               |  24342
               |  4241
               |  42412
     <suf> ::= 241
            |  342
            |  412
     <alf> ::= 1 <alf>
            |  2 <alf>
            |  3 <alf>
            |  4 <alf>
            |  ε }