Ybadoo - Soluções em Software Livre
Tutoriais
Linguagens Formais e Autômatos

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

 

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