Exercício 05.227

Desenvolva uma expressão regular sobre o alfabeto Σ = {1, 2, 3, 4} que produza a linguagem L = {w | w possui 2334 ou 3241 ou 4211 como prefixo, 1312 ou 4122 ou 4243 como subpalavra e 1231 ou 2123 ou 3442 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 = ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* (1312 + 4122 + 4243) (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

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 2334 com a subpalavra 4122 resulta na palavra 2334122:

ER = (2334122 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

2. A sobreposição do prefixo 2334 com a subpalavra 4243 resulta na palavra 2334243:

ER = (2334243 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

3. A sobreposição do prefixo 3241 com a subpalavra 1312 resulta na palavra 3241312:

ER = (3241312 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

4. A sobreposição do prefixo 3241 com a subpalavra 4122 resulta na palavra 324122:

ER = (324122 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

5. A sobreposição do prefixo 4211 com a subpalavra 1312 resulta na palavra 4211312:

ER = (4211312 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442))

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 1312 com o sufixo 1231 resulta na palavra 131231:

ER = ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 131231)

2. A sobreposição da subpalavra 1312 com o sufixo 2123 resulta na palavra 1312123:

ER = ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 1312123)

3. A sobreposição da subpalavra 4122 com o sufixo 2123 resulta na palavra 4122123:

ER = ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 4122123)

4. A sobreposição da subpalavra 4243 com o sufixo 3442 resulta na palavra 4243442:

ER = ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 4243442)

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 2334122 com a sobreposição da subpalavra/sufixo 4122123 resulta na palavra 2334122123:

ER = (2334122123)

2. A sobreposição do prefixo/subpalavra 2334243 com a sobreposição da subpalavra/sufixo 4243442 resulta na palavra 2334243442:

ER = (2334243442)

3. A sobreposição do prefixo/subpalavra 324122 com a sobreposição da subpalavra/sufixo 4122123 resulta na palavra 324122123:

ER = (324122123)

4. A sobreposição do prefixo/subpalavra 3241312 com a sobreposição da subpalavra/sufixo 1312123 resulta na palavra 3241312123:

ER = (3241312123)

5. A sobreposição do prefixo/subpalavra 3241312 com a sobreposição da subpalavra/sufixo 131231 resulta na palavra 324131231:

ER = (324131231)

6. A sobreposição do prefixo/subpalavra 4211312 com a sobreposição da subpalavra/sufixo 1312123 resulta na palavra 4211312123:

ER = (4211312123)

7. A sobreposição do prefixo/subpalavra 4211312 com a sobreposição da subpalavra/sufixo 131231 resulta na palavra 421131231:

ER = (421131231)

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

ER = (((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* (1312 + 4122 + 4243) (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      (2334122 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      (2334243 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      (324122 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      (3241312 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      (4211312 (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 1312123) +
      ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 131231) +
      ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 4122123) +
      ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* 4243442) +
      (2334122123) +
      (2334243442) +
      (324122123) +
      (3241312123) +
      (324131231) +
      (4211312123) +
      (421131231))

É 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 = (((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* (1312 + 4122 + 4243) (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      ((2334122 + 2334243 + 324122 + 3241312 + 4211312) (1 + 2 + 3 + 4)* (1231 + 2123 + 3442)) +
      ((2334 + 3241 + 4211) (1 + 2 + 3 + 4)* (1312123 + 131231 + 4122123 + 4243442)) +
      (2334122123 + 2334243442 + 324122123 + 3241312123 + 324131231 + 4211312123 + 421131231))

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