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

Exercício 05.200

Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b, c, d} que produza a linguagem L = {w | w possui abc ou bcd ou cdd como prefixo, cab ou cda ou dba como subpalavra e adb ou bca 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 = ((abc + bcd + cdd) (a + b + c + d)* (cab + cda + dba) (a + b + c + d)* (adb + bca + 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 abc com a subpalavra cab resulta na palavra abcab:

ER = (abcab (a + b + c + d)* (adb + bca + dad))

2. A sobreposição do prefixo abc com a subpalavra cda resulta na palavra abcda:

ER = (abcda (a + b + c + d)* (adb + bca + dad))

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

ER = (bcda (a + b + c + d)* (adb + bca + dad))

4. A sobreposição do prefixo bcd com a subpalavra dba resulta na palavra bcdba:

ER = (bcdba (a + b + c + d)* (adb + bca + dad))

5. A sobreposição do prefixo cdd com a subpalavra dba resulta na palavra cddba:

ER = (cddba (a + b + c + d)* (adb + bca + 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 cab com o sufixo bca resulta na palavra cabca:

ER = ((abc + bcd + cdd) (a + b + c + d)* cabca)

2. A sobreposição da subpalavra cda com o sufixo adb resulta na palavra cdadb:

ER = ((abc + bcd + cdd) (a + b + c + d)* cdadb)

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

ER = ((abc + bcd + cdd) (a + b + c + d)* cdad)

4. A sobreposição da subpalavra dba com o sufixo adb resulta na palavra dbadb:

ER = ((abc + bcd + cdd) (a + b + c + d)* dbadb)

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 abcab com a sobreposição da subpalavra/sufixo cabca resulta na palavra abcabca:

ER = (abcabca)

2. A sobreposição do prefixo/subpalavra abcda com a sobreposição da subpalavra/sufixo cdad resulta na palavra abcdad:

ER = (abcdad)

3. A sobreposição do prefixo/subpalavra abcda com a sobreposição da subpalavra/sufixo cdadb resulta na palavra abcdadb:

ER = (abcdadb)

4. A sobreposição do prefixo/subpalavra bcda com a sobreposição da subpalavra/sufixo cdad resulta na palavra bcdad:

ER = (bcdad)

5. A sobreposição do prefixo/subpalavra bcda com a sobreposição da subpalavra/sufixo cdadb resulta na palavra bcdadb:

ER = (bcdadb)

6. A sobreposição do prefixo/subpalavra bcdba com a sobreposição da subpalavra/sufixo dbadb resulta na palavra bcdbadb:

ER = (bcdbadb)

7. A sobreposição do prefixo/subpalavra cddba com a sobreposição da subpalavra/sufixo dbadb resulta na palavra cddbadb:

ER = (cddbadb)

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

ER = (((abc + bcd + cdd) (a + b + c + d)* (cab + cda + dba) (a + b + c + d)* (adb + bca + dad)) +
      (abcab (a + b + c + d)* (adb + bca + dad)) +
      (abcda (a + b + c + d)* (adb + bca + dad)) +
      (bcda (a + b + c + d)* (adb + bca + dad)) +
      (bcdba (a + b + c + d)* (adb + bca + dad)) +
      (cddba (a + b + c + d)* (adb + bca + dad)) +
      ((abc + bcd + cdd) (a + b + c + d)* cabca) +
      ((abc + bcd + cdd) (a + b + c + d)* cdad) +
      ((abc + bcd + cdd) (a + b + c + d)* cdadb) +
      ((abc + bcd + cdd) (a + b + c + d)* dbadb) +
      (abcabca) +
      (abcdad) +
      (abcdadb) +
      (bcdad) +
      (bcdadb) +
      (bcdbadb) +
      (cddbadb))

É 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 = (((abc + bcd + cdd) (a + b + c + d)* (cab + cda + dba) (a + b + c + d)* (adb + bca + dad)) +
      ((abcab + abcda + bcda + bcdba + cddba) (a + b + c + d)* (adb + bca + dad)) +
      ((abc + bcd + cdd) (a + b + c + d)* (cabca + cdad + cdadb + dbadb)) +
      (abcabca + abcdad + abcdadb + bcdad + bcdadb + bcdbadb + cddbadb))