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

Exercício 05.169

Desenvolva uma expressão regular sobre o alfabeto Σ = {x, y, z} que produza a linguagem L = {w | w possui xxy ou zyy como prefixo, xyx ou yzx como subpalavra e xxz ou zxy 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 = ((xxy + zyy) (x + y + z)* (xyx + yzx) (x + y + z)* (xxz + zxy))

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 xxy com a subpalavra xyx resulta na palavra xxyx:

ER = (xxyx (x + y + z)* (xxz + zxy))

2. A sobreposição do prefixo xxy com a subpalavra yzx resulta na palavra xxyzx:

ER = (xxyzx (x + y + z)* (xxz + zxy))

3. A sobreposição do prefixo zyy com a subpalavra yzx resulta na palavra zyyzx:

ER = (zyyzx (x + y + z)* (xxz + zxy))

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 xyx com o sufixo xxz resulta na palavra xyxxz:

ER = ((xxy + zyy) (x + y + z)* xyxxz)

2. A sobreposição da subpalavra yzx com o sufixo xxz resulta na palavra yzxxz:

ER = ((xxy + zyy) (x + y + z)* yzxxz)

3. A sobreposição da subpalavra yzx com o sufixo zxy resulta na palavra yzxy:

ER = ((xxy + zyy) (x + y + z)* yzxy)

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 xxyx com a sobreposição da subpalavra/sufixo xyxxz resulta na palavra xxyxxz:

ER = (xxyxxz)

2. A sobreposição do prefixo/subpalavra xxyzx com a sobreposição da subpalavra/sufixo yzxxz resulta na palavra xxyzxxz:

ER = (xxyzxxz)

3. A sobreposição do prefixo/subpalavra xxyzx com a sobreposição da subpalavra/sufixo yzxy resulta na palavra xxyzxy:

ER = (xxyzxy)

4. A sobreposição do prefixo/subpalavra zyyzx com a sobreposição da subpalavra/sufixo yzxxz resulta na palavra zyyzxxz:

ER = (zyyzxxz)

5. A sobreposição do prefixo/subpalavra zyyzx com a sobreposição da subpalavra/sufixo yzxy resulta na palavra zyyzxy:

ER = (zyyzxy)

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

ER = (((xxy + zyy) (x + y + z)* (xyx + yzx) (x + y + z)* (xxz + zxy)) +
      (xxyx (x + y + z)* (xxz + zxy)) +
      (xxyzx (x + y + z)* (xxz + zxy)) +
      (zyyzx (x + y + z)* (xxz + zxy)) +
      ((xxy + zyy) (x + y + z)* xyxxz) +
      ((xxy + zyy) (x + y + z)* yzxxz) +
      ((xxy + zyy) (x + y + z)* yzxy) +
      (xxyxxz) +
      (xxyzxxz) +
      (xxyzxy) +
      (zyyzxxz) +
      (zyyzxy))

É 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 = (((xxy + zyy) (x + y + z)* (xyx + yzx) (x + y + z)* (xxz + zxy)) +
      ((xxyx + xxyzx + zyyzx) (x + y + z)* (xxz + zxy)) +
      ((xxy + zyy) (x + y + z)* (xyxxz + yzxxz + yzxy)) +
      (xxyxxz + xxyzxxz + xxyzxy + zyyzxxz + zyyzxy))