Exercício 05.206

Desenvolva uma expressão regular sobre o alfabeto Σ = {1, 2, 3, 4} que produza 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}.

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 = ((124 + 323 + 432) (1 + 2 + 3 + 4)* (233 + 2434 + 424) (1 + 2 + 3 + 4)* (241 + 342 + 412))

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 124 com a subpalavra 2434 resulta na palavra 12434:

ER = (12434 (1 + 2 + 3 + 4)* (241 + 342 + 412))

2. A sobreposição do prefixo 124 com a subpalavra 424 resulta na palavra 12424:

ER = (12424 (1 + 2 + 3 + 4)* (241 + 342 + 412))

3. A sobreposição do prefixo 323 com a subpalavra 233 resulta na palavra 3233:

ER = (3233 (1 + 2 + 3 + 4)* (241 + 342 + 412))

4. A sobreposição do prefixo 432 com a subpalavra 233 resulta na palavra 43233:

ER = (43233 (1 + 2 + 3 + 4)* (241 + 342 + 412))

5. A sobreposição do prefixo 432 com a subpalavra 2434 resulta na palavra 432434:

ER = (432434 (1 + 2 + 3 + 4)* (241 + 342 + 412))

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 233 com o sufixo 342 resulta na palavra 23342:

ER = ((124 + 323 + 432) (1 + 2 + 3 + 4)* 23342)

2. A sobreposição da subpalavra 2434 com o sufixo 342 resulta na palavra 24342:

ER = ((124 + 323 + 432) (1 + 2 + 3 + 4)* 24342)

3. A sobreposição da subpalavra 2434 com o sufixo 412 resulta na palavra 243412:

ER = ((124 + 323 + 432) (1 + 2 + 3 + 4)* 243412)

4. A sobreposição da subpalavra 424 com o sufixo 241 resulta na palavra 4241:

ER = ((124 + 323 + 432) (1 + 2 + 3 + 4)* 4241)

5. A sobreposição da subpalavra 424 com o sufixo 412 resulta na palavra 42412:

ER = ((124 + 323 + 432) (1 + 2 + 3 + 4)* 42412)

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 12424 com a sobreposição da subpalavra/sufixo 4241 resulta na palavra 124241:

ER = (124241)

2. A sobreposição do prefixo/subpalavra 12424 com a sobreposição da subpalavra/sufixo 42412 resulta na palavra 1242412:

ER = (1242412)

3. A sobreposição do prefixo/subpalavra 12434 com a sobreposição da subpalavra/sufixo 243412 resulta na palavra 1243412:

ER = (1243412)

4. A sobreposição do prefixo/subpalavra 12434 com a sobreposição da subpalavra/sufixo 24342 resulta na palavra 124342:

ER = (124342)

5. A sobreposição do prefixo/subpalavra 3233 com a sobreposição da subpalavra/sufixo 23342 resulta na palavra 323342:

ER = (323342)

6. A sobreposição do prefixo/subpalavra 43233 com a sobreposição da subpalavra/sufixo 23342 resulta na palavra 4323342:

ER = (4323342)

7. A sobreposição do prefixo/subpalavra 432434 com a sobreposição da subpalavra/sufixo 243412 resulta na palavra 43243412:

ER = (43243412)

8. A sobreposição do prefixo/subpalavra 432434 com a sobreposição da subpalavra/sufixo 24342 resulta na palavra 4324342:

ER = (4324342)

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

ER = (((124 + 323 + 432) (1 + 2 + 3 + 4)* (233 + 2434 + 424) (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      (12424 (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      (12434 (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      (3233 (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      (43233 (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      (432434 (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* 23342) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* 243412) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* 24342) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* 4241) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* 42412) +
      (124241) +
      (1242412) +
      (1243412) +
      (124342) +
      (323342) +
      (4323342) +
      (43243412) +
      (4324342))

É 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 = (((124 + 323 + 432) (1 + 2 + 3 + 4)* (233 + 2434 + 424) (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      ((12424 + 12434 + 3233 + 43233 + 432434) (1 + 2 + 3 + 4)* (241 + 342 + 412)) +
      ((124 + 323 + 432) (1 + 2 + 3 + 4)* (23342 + 243412 + 24342 + 4241 + 42412)) +
      (124241 + 1242412 + 1243412 + 124342 + 323342 + 4323342 + 43243412 + 4324342))

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