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.203

Exercício 05.203

Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b, c, d} que produza a linguagem L = {w | w possui ab ou bca ou bcda como prefixo, acab ou cad ou dab como subpalavra e aba ou bbc ou dad 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 = ((ab + bca + bcda) (a + b + c + d)* (acab + cad + dab) (a + b + c + d)* (aba + bbc + dad))

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 bca com a subpalavra acab resulta na palavra bcacab:

ER = (bcacab (a + b + c + d)* (aba + bbc + dad))

2. A sobreposição do prefixo bca com a subpalavra cad resulta na palavra bcad:

ER = (bcad (a + b + c + d)* (aba + bbc + dad))

3. A sobreposição do prefixo bcda com a subpalavra acab resulta na palavra bcdacab:

ER = (bcdacab (a + b + c + d)* (aba + bbc + dad))

4. A sobreposição do prefixo bcda com a subpalavra dab resulta na palavra bcdab:

ER = (bcdab (a + b + c + d)* (aba + bbc + dad))

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 acab com o sufixo aba resulta na palavra acaba:

ER = ((ab + bca + bcda) (a + b + c + d)* acaba)

2. A sobreposição da subpalavra acab com o sufixo bbc resulta na palavra acabbc:

ER = ((ab + bca + bcda) (a + b + c + d)* acabbc)

3. A sobreposição da subpalavra cad com o sufixo dad resulta na palavra cadad:

ER = ((ab + bca + bcda) (a + b + c + d)* cadad)

4. A sobreposição da subpalavra dab com o sufixo aba resulta na palavra daba:

ER = ((ab + bca + bcda) (a + b + c + d)* daba)

5. A sobreposição da subpalavra dab com o sufixo bbc resulta na palavra dabbc:

ER = ((ab + bca + bcda) (a + b + c + d)* dabbc)

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 bcacab com a sobreposição da subpalavra/sufixo acaba resulta na palavra bcacaba:

ER = (bcacaba)

2. A sobreposição do prefixo/subpalavra bcacab com a sobreposição da subpalavra/sufixo acabbc resulta na palavra bcacabbc:

ER = (bcacabbc)

3. A sobreposição do prefixo/subpalavra bcad com a sobreposição da subpalavra/sufixo cadad resulta na palavra bcadad:

ER = (bcadad)

4. A sobreposição do prefixo/subpalavra bcdab com a sobreposição da subpalavra/sufixo daba resulta na palavra bcdaba:

ER = (bcdaba)

5. A sobreposição do prefixo/subpalavra bcdab com a sobreposição da subpalavra/sufixo dabbc resulta na palavra bcdabbc:

ER = (bcdabbc)

6. A sobreposição do prefixo/subpalavra bcdacab com a sobreposição da subpalavra/sufixo acaba resulta na palavra bcdacaba:

ER = (bcdacaba)

7. A sobreposição do prefixo/subpalavra bcdacab com a sobreposição da subpalavra/sufixo acabbc resulta na palavra bcdacabbc:

ER = (bcdacabbc)

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

ER = (((ab + bca + bcda) (a + b + c + d)* (acab + cad + dab) (a + b + c + d)* (aba + bbc + dad)) +
      (bcacab (a + b + c + d)* (aba + bbc + dad)) +
      (bcad (a + b + c + d)* (aba + bbc + dad)) +
      (bcdab (a + b + c + d)* (aba + bbc + dad)) +
      (bcdacab (a + b + c + d)* (aba + bbc + dad)) +
      ((ab + bca + bcda) (a + b + c + d)* acaba) +
      ((ab + bca + bcda) (a + b + c + d)* acabbc) +
      ((ab + bca + bcda) (a + b + c + d)* cadad) +
      ((ab + bca + bcda) (a + b + c + d)* daba) +
      ((ab + bca + bcda) (a + b + c + d)* dabbc) +
      (bcacaba) +
      (bcacabbc) +
      (bcadad) +
      (bcdaba) +
      (bcdabbc) +
      (bcdacaba) +
      (bcdacabbc))

É 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 = (((ab + bca + bcda) (a + b + c + d)* (acab + cad + dab) (a + b + c + d)* (aba + bbc + dad)) +
      ((bcacab + bcad + bcdab + bcdacab) (a + b + c + d)* (aba + bbc + dad)) +
      ((ab + bca + bcda) (a + b + c + d)* (acaba + acabbc + cadad + daba + dabbc)) +
      (bcacaba + bcacabbc + bcadad + bcdaba + bcdabbc + bcdacaba + bcdacabbc))