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

Exercício 05.205

Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b, c, d} que produza a linguagem L = {w | w possui ba ou bab ou dac como prefixo, abb ou acbc ou cac como subpalavra e acd ou bca ou cda 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 = ((ba + bab + dac) (a + b + c + d)* (abb + acbc + cac) (a + b + c + d)* (acd + bca + cda))

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 ba com a subpalavra abb resulta na palavra babb:

ER = (babb (a + b + c + d)* (acd + bca + cda))

2. A sobreposição do prefixo ba com a subpalavra acbc resulta na palavra bacbc:

ER = (bacbc (a + b + c + d)* (acd + bca + cda))

3. A sobreposição do prefixo bab com a subpalavra abb resulta na palavra babb:

ER = (babb (a + b + c + d)* (acd + bca + cda))

4. A sobreposição do prefixo dac com a subpalavra acbc resulta na palavra dacbc:

ER = (dacbc (a + b + c + d)* (acd + bca + cda))

5. A sobreposição do prefixo dac com a subpalavra cac resulta na palavra dacac:

ER = (dacac (a + b + c + d)* (acd + bca + cda))

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 abb com o sufixo bca resulta na palavra abbca:

ER = ((ba + bab + dac) (a + b + c + d)* abbca)

2. A sobreposição da subpalavra acbc com o sufixo bca resulta na palavra acbca:

ER = ((ba + bab + dac) (a + b + c + d)* acbca)

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

ER = ((ba + bab + dac) (a + b + c + d)* acbcda)

4. A sobreposição da subpalavra cac com o sufixo acd resulta na palavra cacd:

ER = ((ba + bab + dac) (a + b + c + d)* cacd)

5. A sobreposição da subpalavra cac com o sufixo cda resulta na palavra cacda:

ER = ((ba + bab + dac) (a + b + c + d)* cacda)

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 babb com a sobreposição da subpalavra/sufixo abbca resulta na palavra babbca:

ER = (babbca)

2. A sobreposição do prefixo/subpalavra bacbc com a sobreposição da subpalavra/sufixo acbca resulta na palavra bacbca:

ER = (bacbca)

3. A sobreposição do prefixo/subpalavra bacbc com a sobreposição da subpalavra/sufixo acbcda resulta na palavra bacbcda:

ER = (bacbcda)

4. A sobreposição do prefixo/subpalavra dacac com a sobreposição da subpalavra/sufixo cacd resulta na palavra dacacd:

ER = (dacacd)

5. A sobreposição do prefixo/subpalavra dacac com a sobreposição da subpalavra/sufixo cacda resulta na palavra dacacda:

ER = (dacacda)

6. A sobreposição do prefixo/subpalavra dacbc com a sobreposição da subpalavra/sufixo acbca resulta na palavra dacbca:

ER = (dacbca)

7. A sobreposição do prefixo/subpalavra dacbc com a sobreposição da subpalavra/sufixo acbcda resulta na palavra dacbcda:

ER = (dacbcda)

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

ER = (((ba + bab + dac) (a + b + c + d)* (abb + acbc + cac) (a + b + c + d)* (acd + bca + cda)) +
      (babb (a + b + c + d)* (acd + bca + cda)) +
      (bacbc (a + b + c + d)* (acd + bca + cda)) +
      (dacac (a + b + c + d)* (acd + bca + cda)) +
      (dacbc (a + b + c + d)* (acd + bca + cda)) +
      ((ba + bab + dac) (a + b + c + d)* abbca) +
      ((ba + bab + dac) (a + b + c + d)* acbca) +
      ((ba + bab + dac) (a + b + c + d)* acbcda) +
      ((ba + bab + dac) (a + b + c + d)* cacd) +
      ((ba + bab + dac) (a + b + c + d)* cacda) +
      (babbca) +
      (bacbca) +
      (bacbcda) +
      (dacacd) +
      (dacacda) +
      (dacbca) +
      (dacbcda))

É 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 = (((ba + bab + dac) (a + b + c + d)* (abb + acbc + cac) (a + b + c + d)* (acd + bca + cda)) +
      ((babb + bacbc + dacac + dacbc) (a + b + c + d)* (acd + bca + cda)) +
      ((ba + bab + dac) (a + b + c + d)* (abbca + acbca + acbcda + cacd + cacda)) +
      (babbca + bacbca + bacbcda + dacacd + dacacda + dacbca + dacbcda))