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))