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

Exercício 05.217

Desenvolva uma expressão regular sobre o alfabeto Σ = {i, j, k} que produza a linguagem L = {w | w possui iik ou jkj ou kji como prefixo, ikki ou jiik ou kjji como subpalavra e ikk ou jii ou kkj 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 = ((iik + jkj + kji) (i + j + k)* (ikki + jiik + kjji) (i + j + k)* (ikk + jii + kkj))

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 iik com a subpalavra ikki resulta na palavra iikki:

ER = (iikki (i + j + k)* (ikk + jii + kkj))

2. A sobreposição do prefixo iik com a subpalavra kjji resulta na palavra iikjji:

ER = (iikjji (i + j + k)* (ikk + jii + kkj))

3. A sobreposição do prefixo jkj com a subpalavra jiik resulta na palavra jkjiik:

ER = (jkjiik (i + j + k)* (ikk + jii + kkj))

4. A sobreposição do prefixo jkj com a subpalavra kjji resulta na palavra jkjji:

ER = (jkjji (i + j + k)* (ikk + jii + kkj))

5. A sobreposição do prefixo kji com a subpalavra ikki resulta na palavra kjikki:

ER = (kjikki (i + j + k)* (ikk + jii + kkj))

6. A sobreposição do prefixo kji com a subpalavra jiik resulta na palavra kjiik:

ER = (kjiik (i + j + k)* (ikk + jii + kkj))

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 ikki com o sufixo ikk resulta na palavra ikkikk:

ER = ((iik + jkj + kji) (i + j + k)* ikkikk)

2. A sobreposição da subpalavra jiik com o sufixo ikk resulta na palavra jiikk:

ER = ((iik + jkj + kji) (i + j + k)* jiikk)

3. A sobreposição da subpalavra jiik com o sufixo kkj resulta na palavra jiikkj:

ER = ((iik + jkj + kji) (i + j + k)* jiikkj)

4. A sobreposição da subpalavra kjji com o sufixo ikk resulta na palavra kjjikk:

ER = ((iik + jkj + kji) (i + j + k)* kjjikk)

5. A sobreposição da subpalavra kjji com o sufixo jii resulta na palavra kjjii:

ER = ((iik + jkj + kji) (i + j + k)* kjjii)

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 iikjji com a sobreposição da subpalavra/sufixo kjjii resulta na palavra iikjjii:

ER = (iikjjii)

2. A sobreposição do prefixo/subpalavra iikjji com a sobreposição da subpalavra/sufixo kjjikk resulta na palavra iikjjikk:

ER = (iikjjikk)

3. A sobreposição do prefixo/subpalavra iikki com a sobreposição da subpalavra/sufixo ikkikk resulta na palavra iikkikk:

ER = (iikkikk)

4. A sobreposição do prefixo/subpalavra jkjiik com a sobreposição da subpalavra/sufixo jiikk resulta na palavra jkjiikk:

ER = (jkjiikk)

5. A sobreposição do prefixo/subpalavra jkjiik com a sobreposição da subpalavra/sufixo jiikkj resulta na palavra jkjiikkj:

ER = (jkjiikkj)

6. A sobreposição do prefixo/subpalavra jkjji com a sobreposição da subpalavra/sufixo kjjii resulta na palavra jkjjii:

ER = (jkjjii)

7. A sobreposição do prefixo/subpalavra jkjji com a sobreposição da subpalavra/sufixo kjjikk resulta na palavra jkjjikk:

ER = (jkjjikk)

8. A sobreposição do prefixo/subpalavra kjiik com a sobreposição da subpalavra/sufixo jiikk resulta na palavra kjiikk:

ER = (kjiikk)

9. A sobreposição do prefixo/subpalavra kjiik com a sobreposição da subpalavra/sufixo jiikkj resulta na palavra kjiikkj:

ER = (kjiikkj)

10. A sobreposição do prefixo/subpalavra kjikki com a sobreposição da subpalavra/sufixo ikkikk resulta na palavra kjikkikk:

ER = (kjikkikk)

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

ER = (((iik + jkj + kji) (i + j + k)* (ikki + jiik + kjji) (i + j + k)* (ikk + jii + kkj)) +
      (iikjji (i + j + k)* (ikk + jii + kkj)) +
      (iikki (i + j + k)* (ikk + jii + kkj)) +
      (jkjiik (i + j + k)* (ikk + jii + kkj)) +
      (jkjji (i + j + k)* (ikk + jii + kkj)) +
      (kjiik (i + j + k)* (ikk + jii + kkj)) +
      (kjikki (i + j + k)* (ikk + jii + kkj)) +
      ((iik + jkj + kji) (i + j + k)* ikkikk) +
      ((iik + jkj + kji) (i + j + k)* jiikk) +
      ((iik + jkj + kji) (i + j + k)* jiikkj) +
      ((iik + jkj + kji) (i + j + k)* kjjii) +
      ((iik + jkj + kji) (i + j + k)* kjjikk) +
      (iikjjii) +
      (iikjjikk) +
      (iikkikk) +
      (jkjiikk) +
      (jkjiikkj) +
      (jkjjii) +
      (jkjjikk) +
      (kjiikk) +
      (kjiikkj) +
      (kjikkikk))

É 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 = (((iik + jkj + kji) (i + j + k)* (ikki + jiik + kjji) (i + j + k)* (ikk + jii + kkj)) +
      ((iikjji + iikki + jkjiik + jkjji + kjiik + kjikki) (i + j + k)* (ikk + jii + kkj)) +
      ((iik + jkj + kji) (i + j + k)* (ikkikk + jiikk + jiikkj + kjjii + kjjikk)) +
      (iikjjii + iikjjikk + iikkikk + jkjiikk + jkjiikkj + jkjjii + jkjjikk + kjiikk + kjiikkj + kjikkikk))