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

Exercício 05.238

Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b, c, d} que produza a linguagem L = {w | w possui bcbc ou dabc ou dada como prefixo, aabc ou bcda ou ccad ou dacb como subpalavra e aada ou acbd ou bccc ou ddab 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 = ((bcbc + dabc + dada) (a + b + c + d)* (aabc + bcda + ccad + dacb) (a + b + c + d)* (aada + acbd + bccc + ddab))

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 bcbc com a subpalavra bcda resulta na palavra bcbcda:

ER = (bcbcda (a + b + c + d)* (aada + acbd + bccc + ddab))

2. A sobreposição do prefixo bcbc com a subpalavra ccad resulta na palavra bcbccad:

ER = (bcbccad (a + b + c + d)* (aada + acbd + bccc + ddab))

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

ER = (dabcda (a + b + c + d)* (aada + acbd + bccc + ddab))

4. A sobreposição do prefixo dabc com a subpalavra ccad resulta na palavra dabccad:

ER = (dabccad (a + b + c + d)* (aada + acbd + bccc + ddab))

5. A sobreposição do prefixo dada com a subpalavra aabc resulta na palavra dadaabc:

ER = (dadaabc (a + b + c + d)* (aada + acbd + bccc + ddab))

6. A sobreposição do prefixo dada com a subpalavra dacb resulta na palavra dadacb:

ER = (dadacb (a + b + c + d)* (aada + acbd + bccc + ddab))

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 aabc com o sufixo bccc resulta na palavra aabccc:

ER = ((bcbc + dabc + dada) (a + b + c + d)* aabccc)

2. A sobreposição da subpalavra bcda com o sufixo aada resulta na palavra bcdaada:

ER = ((bcbc + dabc + dada) (a + b + c + d)* bcdaada)

3. A sobreposição da subpalavra bcda com o sufixo acbd resulta na palavra bcdacbd:

ER = ((bcbc + dabc + dada) (a + b + c + d)* bcdacbd)

4. A sobreposição da subpalavra ccad com o sufixo ddab resulta na palavra ccaddab:

ER = ((bcbc + dabc + dada) (a + b + c + d)* ccaddab)

5. A sobreposição da subpalavra dacb com o sufixo acbd resulta na palavra dacbd:

ER = ((bcbc + dabc + dada) (a + b + c + d)* dacbd)

6. A sobreposição da subpalavra dacb com o sufixo bccc resulta na palavra dacbccc:

ER = ((bcbc + dabc + dada) (a + b + c + d)* dacbccc)

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 bcbccad com a sobreposição da subpalavra/sufixo ccaddab resulta na palavra bcbccaddab:

ER = (bcbccaddab)

2. A sobreposição do prefixo/subpalavra bcbcda com a sobreposição da subpalavra/sufixo bcdaada resulta na palavra bcbcdaada:

ER = (bcbcdaada)

3. A sobreposição do prefixo/subpalavra bcbcda com a sobreposição da subpalavra/sufixo bcdacbd resulta na palavra bcbcdacbd:

ER = (bcbcdacbd)

4. A sobreposição do prefixo/subpalavra dabccad com a sobreposição da subpalavra/sufixo ccaddab resulta na palavra dabccaddab:

ER = (dabccaddab)

5. A sobreposição do prefixo/subpalavra dabcda com a sobreposição da subpalavra/sufixo bcdaada resulta na palavra dabcdaada:

ER = (dabcdaada)

6. A sobreposição do prefixo/subpalavra dabcda com a sobreposição da subpalavra/sufixo bcdacbd resulta na palavra dabcdacbd:

ER = (dabcdacbd)

7. A sobreposição do prefixo/subpalavra dadaabc com a sobreposição da subpalavra/sufixo aabccc resulta na palavra dadaabccc:

ER = (dadaabccc)

8. A sobreposição do prefixo/subpalavra dadacb com a sobreposição da subpalavra/sufixo dacbccc resulta na palavra dadacbccc:

ER = (dadacbccc)

9. A sobreposição do prefixo/subpalavra dadacb com a sobreposição da subpalavra/sufixo dacbd resulta na palavra dadacbd:

ER = (dadacbd)

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

ER = (((bcbc + dabc + dada) (a + b + c + d)* (aabc + bcda + ccad + dacb) (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (bcbccad (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (bcbcda (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (dabccad (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (dabcda (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (dadaabc (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      (dadacb (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      ((bcbc + dabc + dada) (a + b + c + d)* aabccc) +
      ((bcbc + dabc + dada) (a + b + c + d)* bcdaada) +
      ((bcbc + dabc + dada) (a + b + c + d)* bcdacbd) +
      ((bcbc + dabc + dada) (a + b + c + d)* ccaddab) +
      ((bcbc + dabc + dada) (a + b + c + d)* dacbccc) +
      ((bcbc + dabc + dada) (a + b + c + d)* dacbd) +
      (bcbccaddab) +
      (bcbcdaada) +
      (bcbcdacbd) +
      (dabccaddab) +
      (dabcdaada) +
      (dabcdacbd) +
      (dadaabccc) +
      (dadacbccc) +
      (dadacbd))

É 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 = (((bcbc + dabc + dada) (a + b + c + d)* (aabc + bcda + ccad + dacb) (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      ((bcbccad + bcbcda + dabccad + dabcda + dadaabc + dadacb) (a + b + c + d)* (aada + acbd + bccc + ddab)) +
      ((bcbc + dabc + dada) (a + b + c + d)* (aabccc + bcdaada + bcdacbd + ccaddab + dacbccc + dacbd)) +
      (bcbccaddab + bcbcdaada + bcbcdacbd + dabccaddab + dabcdaada + dabcdacbd + dadaabccc + dadacbccc + dadacbd))