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

1. Ybadoo
2. Tutoriais
3. Linguagens Formais e Autômatos
4. Expressões Regulares
5. Exercício 05.146

Exercício 05.146

Desenvolva uma expressão regular sobre o alfabeto Σ = {1, 2, 3} que produza a linguagem L = {w | w possui 121 ou 132 como prefixo, 123 ou 213 como subpalavra e 232 ou 332 como sufixo}.

Solução do Exercício

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 = ((121 + 132) (1 + 2 + 3)* (123 + 213) (1 + 2 + 3)* (232 + 332))

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 121 com a subpalavra 123 resulta na palavra 12123:

ER = (12123 (1 + 2 + 3)* (232 + 332))

2. A sobreposição do prefixo 121 com a subpalavra 213 resulta na palavra 1213:

ER = (1213 (1 + 2 + 3)* (232 + 332))

3. A sobreposição do prefixo 132 com a subpalavra 213 resulta na palavra 13213:

ER = (13213 (1 + 2 + 3)* (232 + 332))

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 123 com o sufixo 232 resulta na palavra 1232:

ER = ((121 + 132) (1 + 2 + 3)* 1232)

2. A sobreposição da subpalavra 123 com o sufixo 332 resulta na palavra 12332:

ER = ((121 + 132) (1 + 2 + 3)* 12332)

3. A sobreposição da subpalavra 213 com o sufixo 332 resulta na palavra 21332:

ER = ((121 + 132) (1 + 2 + 3)* 21332)

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 12123 com a sobreposição da subpalavra/sufixo 1232 resulta na palavra 121232:

ER = (121232)

2. A sobreposição do prefixo/subpalavra 12123 com a sobreposição da subpalavra/sufixo 12332 resulta na palavra 1212332:

ER = (1212332)

3. A sobreposição do prefixo/subpalavra 1213 com a sobreposição da subpalavra/sufixo 21332 resulta na palavra 121332:

ER = (121332)

4. A sobreposição do prefixo/subpalavra 13213 com a sobreposição da subpalavra/sufixo 21332 resulta na palavra 1321332:

ER = (1321332)

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

ER = (((121 + 132) (1 + 2 + 3)* (123 + 213) (1 + 2 + 3)* (232 + 332)) +
      (12123 (1 + 2 + 3)* (232 + 332)) +
      (1213 (1 + 2 + 3)* (232 + 332)) +
      (13213 (1 + 2 + 3)* (232 + 332)) +
      ((121 + 132) (1 + 2 + 3)* 1232) +
      ((121 + 132) (1 + 2 + 3)* 12332) +
      ((121 + 132) (1 + 2 + 3)* 21332) +
      (121232) +
      (1212332) +
      (121332) +
      (1321332))

É 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 = (((121 + 132) (1 + 2 + 3)* (123 + 213) (1 + 2 + 3)* (232 + 332)) +
      ((12123 + 1213 + 13213) (1 + 2 + 3)* (232 + 332)) +
      ((121 + 132) (1 + 2 + 3)* (1232 + 12332 + 21332)) +
      (121232 + 1212332 + 121332 + 1321332))