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

Exercício 05.168

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

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 yxz resulta na palavra xxyxz:

ER = (xxyxz (x + y + z)* (xyx + xzz))

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

ER = (xxyzx (x + y + z)* (xyx + xzz))

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

ER = (yyzx (x + y + z)* (xyx + xzz))

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 yxz com o sufixo xzz resulta na palavra yxzz:

ER = ((xxy + yyz) (x + y + z)* yxzz)

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

ER = ((xxy + yyz) (x + y + z)* yzxyx)

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

ER = ((xxy + yyz) (x + y + z)* yzxzz)

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 xxyxz com a sobreposição da subpalavra/sufixo yxzz resulta na palavra xxyxzz:

ER = (xxyxzz)

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

ER = (xxyzxyx)

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

ER = (xxyzxzz)

4. A sobreposição do prefixo/subpalavra yyzx com a sobreposição da subpalavra/sufixo yzxyx resulta na palavra yyzxyx:

ER = (yyzxyx)

5. A sobreposição do prefixo/subpalavra yyzx com a sobreposição da subpalavra/sufixo yzxzz resulta na palavra yyzxzz:

ER = (yyzxzz)

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

ER = (((xxy + yyz) (x + y + z)* (yxz + yzx) (x + y + z)* (xyx + xzz)) +
      (xxyxz (x + y + z)* (xyx + xzz)) +
      (xxyzx (x + y + z)* (xyx + xzz)) +
      (yyzx (x + y + z)* (xyx + xzz)) +
      ((xxy + yyz) (x + y + z)* yxzz) +
      ((xxy + yyz) (x + y + z)* yzxyx) +
      ((xxy + yyz) (x + y + z)* yzxzz) +
      (xxyxzz) +
      (xxyzxyx) +
      (xxyzxzz) +
      (yyzxyx) +
      (yyzxzz))

É 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 + yyz) (x + y + z)* (yxz + yzx) (x + y + z)* (xyx + xzz)) +
      ((xxyxz + xxyzx + yyzx) (x + y + z)* (xyx + xzz)) +
      ((xxy + yyz) (x + y + z)* (yxzz + yzxyx + yzxzz)) +
      (xxyxzz + xxyzxyx + xxyzxzz + yyzxyx + yyzxzz))