Exercício 05.237

Desenvolva uma expressão regular sobre o alfabeto Σ = {1, 2, 3, 4} que produza a linguagem L = {w | w possui 1212 ou 1234 ou 3434 como prefixo, 1243 ou 2234 ou 3412 ou 4421 como subpalavra e 1123 ou 2212 ou 2431 ou 3444 como sufixo}.

Para a classe de problemas abordado no enunciado do exercício, a elaboração da expressão regular que produza a linguagem L, segue o esquema composto por quatro casos, como segue:

ER = (((prefixos)(alfabeto)(subpalavras)(alfabeto)(sufixos)) +
      ((sobreposições prefixos/subpalavras)(alfabeto)(sufixos)) +
      ((prefixos)(alfabeto)(sobreposições subpalavras/sufixos)) +
      (sobreposições prefixos/subpalavras/sufixos))

O primeiro caso considera que não existem sobreposições entre os elementos que definem os prefixos e as subpalavras e nem entre os elementos que definem as subpalavras e os sufixos da linguagem L, como segue:

ER = ((prefixos)(alfabeto)(subpalavras)(alfabeto)(sufixos))

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* (1243 + 2234 + 3412 + 4421) (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

O segundo caso considera a existência de sobreposições entre os elementos que definem os prefixos e as subpalavras da linguagem L, como segue:

ER = ((sobreposições prefixos/subpalavras)(alfabeto)(sufixos))

1. A sobreposição do prefixo 1212 com a subpalavra 1243 resulta na palavra 121243:

ER = (121243 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

2. A sobreposição do prefixo 1212 com a subpalavra 2234 resulta na palavra 1212234:

ER = (1212234 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

3. A sobreposição do prefixo 1234 com a subpalavra 3412 resulta na palavra 123412:

ER = (123412 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

4. A sobreposição do prefixo 1234 com a subpalavra 4421 resulta na palavra 1234421:

ER = (1234421 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

5. A sobreposição do prefixo 3434 com a subpalavra 3412 resulta na palavra 343412:

ER = (343412 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

6. A sobreposição do prefixo 3434 com a subpalavra 4421 resulta na palavra 3434421:

ER = (3434421 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444))

O terceiro caso considera a existência de sobreposições entre os elementos que definem as subpalavras e os sufixos da linguagem L, como segue:

ER = ((prefixos)(alfabeto)(sobreposições subpalavras/sufixos))

1. A sobreposição da subpalavra 1243 com o sufixo 2431 resulta na palavra 12431:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 12431)

2. A sobreposição da subpalavra 1243 com o sufixo 3444 resulta na palavra 1243444:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 1243444)

3. A sobreposição da subpalavra 2234 com o sufixo 3444 resulta na palavra 223444:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 223444)

4. A sobreposição da subpalavra 3412 com o sufixo 2212 resulta na palavra 3412212:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 3412212)

5. A sobreposição da subpalavra 3412 com o sufixo 2431 resulta na palavra 3412431:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 3412431)

6. A sobreposição da subpalavra 4421 com o sufixo 1123 resulta na palavra 4421123:

ER = ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 4421123)

O quarto e último caso considera a existência de sobreposições entre os elementos que definem os prefixos, as subpalavras e os sufixos da linguagem L, como segue:

ER = (sobreposições prefixos/subpalavras/sufixos)

1. A sobreposição do prefixo/subpalavra 1212234 com a sobreposição da subpalavra/sufixo 223444 resulta na palavra 121223444:

ER = (121223444)

2. A sobreposição do prefixo/subpalavra 121243 com a sobreposição da subpalavra/sufixo 12431 resulta na palavra 1212431:

ER = (1212431)

3. A sobreposição do prefixo/subpalavra 121243 com a sobreposição da subpalavra/sufixo 1243444 resulta na palavra 121243444:

ER = (121243444)

4. A sobreposição do prefixo/subpalavra 123412 com a sobreposição da subpalavra/sufixo 3412212 resulta na palavra 123412212:

ER = (123412212)

5. A sobreposição do prefixo/subpalavra 123412 com a sobreposição da subpalavra/sufixo 3412431 resulta na palavra 123412431:

ER = (123412431)

6. A sobreposição do prefixo/subpalavra 1234421 com a sobreposição da subpalavra/sufixo 4421123 resulta na palavra 1234421123:

ER = (1234421123)

7. A sobreposição do prefixo/subpalavra 343412 com a sobreposição da subpalavra/sufixo 3412212 resulta na palavra 343412212:

ER = (343412212)

8. A sobreposição do prefixo/subpalavra 343412 com a sobreposição da subpalavra/sufixo 3412431 resulta na palavra 343412431:

ER = (343412431)

9. A sobreposição do prefixo/subpalavra 3434421 com a sobreposição da subpalavra/sufixo 4421123 resulta na palavra 3434421123:

ER = (3434421123)

Desta forma, a expressão regular que produza a linguagem L é:

ER = (((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* (1243 + 2234 + 3412 + 4421) (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (1212234 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (121243 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (123412 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (1234421 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (343412 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      (3434421 (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 12431) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 1243444) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 223444) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 3412212) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 3412431) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* 4421123) +
      (121223444) +
      (1212431) +
      (121243444) +
      (123412212) +
      (123412431) +
      (1234421123) +
      (343412212) +
      (343412431) +
      (3434421123))

É possível apresentar uma expressão regular mais concisa que produza a linguagem L, agrupando as ocorrências dos casos idênticos numa única expressão, como segue:

ER = (((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* (1243 + 2234 + 3412 + 4421) (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      ((1212234 + 121243 + 123412 + 1234421 + 343412 + 3434421) (1 + 2 + 3 + 4)* (1123 + 2212 + 2431 + 3444)) +
      ((1212 + 1234 + 3434) (1 + 2 + 3 + 4)* (12431 + 1243444 + 223444 + 3412212 + 3412431 + 4421123)) +
      (121223444 + 1212431 + 121243444 + 123412212 + 123412431 + 1234421123 + 343412212 + 343412431 + 3434421123))

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

Solução do Exercício

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