Ybadoo - Soluções em Software Livre
Tutoriais
Linguagens Formais e Autômatos

Desenvolva uma expressão regular sobre o alfabeto Σ = {w, x, y, z} que produza a linguagem L = {w | w possui wxy ou xyy ou zwx como prefixo, xyz ou xzw ou ywz como subpalavra e wxz ou yzy ou zyw como sufixo}.

 

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 = ((wxy + xyy + zwx) (w + x + y + z)* (xyz + xzw + ywz) (w + x + y + z)* (wxz + yzy + zyw))

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 wxy com a subpalavra xyz resulta na palavra wxyz:

ER = (wxyz (w + x + y + z)* (wxz + yzy + zyw))

2. A sobreposição do prefixo wxy com a subpalavra ywz resulta na palavra wxywz:

ER = (wxywz (w + x + y + z)* (wxz + yzy + zyw))

3. A sobreposição do prefixo xyy com a subpalavra ywz resulta na palavra xyywz:

ER = (xyywz (w + x + y + z)* (wxz + yzy + zyw))

4. A sobreposição do prefixo zwx com a subpalavra xyz resulta na palavra zwxyz:

ER = (zwxyz (w + x + y + z)* (wxz + yzy + zyw))

5. A sobreposição do prefixo zwx com a subpalavra xzw resulta na palavra zwxzw:

ER = (zwxzw (w + x + y + z)* (wxz + yzy + zyw))

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 xyz com o sufixo yzy resulta na palavra xyzy:

ER = ((wxy + xyy + zwx) (w + x + y + z)* xyzy)

2. A sobreposição da subpalavra xyz com o sufixo zyw resulta na palavra xyzyw:

ER = ((wxy + xyy + zwx) (w + x + y + z)* xyzyw)

3. A sobreposição da subpalavra xzw com o sufixo wxz resulta na palavra xzwxz:

ER = ((wxy + xyy + zwx) (w + x + y + z)* xzwxz)

4. A sobreposição da subpalavra ywz com o sufixo zyw resulta na palavra ywzyw:

ER = ((wxy + xyy + zwx) (w + x + y + z)* ywzyw)

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 wxywz com a sobreposição da subpalavra/sufixo ywzyw resulta na palavra wxywzyw:

ER = (wxywzyw)

2. A sobreposição do prefixo/subpalavra wxyz com a sobreposição da subpalavra/sufixo xyzy resulta na palavra wxyzy:

ER = (wxyzy)

3. A sobreposição do prefixo/subpalavra wxyz com a sobreposição da subpalavra/sufixo xyzyw resulta na palavra wxyzyw:

ER = (wxyzyw)

4. A sobreposição do prefixo/subpalavra xyywz com a sobreposição da subpalavra/sufixo ywzyw resulta na palavra xyywzyw:

ER = (xyywzyw)

5. A sobreposição do prefixo/subpalavra zwxyz com a sobreposição da subpalavra/sufixo xyzy resulta na palavra zwxyzy:

ER = (zwxyzy)

6. A sobreposição do prefixo/subpalavra zwxyz com a sobreposição da subpalavra/sufixo xyzyw resulta na palavra zwxyzyw:

ER = (zwxyzyw)

7. A sobreposição do prefixo/subpalavra zwxzw com a sobreposição da subpalavra/sufixo xzwxz resulta na palavra zwxzwxz:

ER = (zwxzwxz)

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

ER = (((wxy + xyy + zwx) (w + x + y + z)* (xyz + xzw + ywz) (w + x + y + z)* (wxz + yzy + zyw)) +
(wxywz (w + x + y + z)* (wxz + yzy + zyw)) +
(wxyz (w + x + y + z)* (wxz + yzy + zyw)) +
(xyywz (w + x + y + z)* (wxz + yzy + zyw)) +
(zwxyz (w + x + y + z)* (wxz + yzy + zyw)) +
(zwxzw (w + x + y + z)* (wxz + yzy + zyw)) +
((wxy + xyy + zwx) (w + x + y + z)* xyzy) +
((wxy + xyy + zwx) (w + x + y + z)* xyzyw) +
((wxy + xyy + zwx) (w + x + y + z)* xzwxz) +
((wxy + xyy + zwx) (w + x + y + z)* ywzyw) +
(wxywzyw) +
(wxyzy) +
(wxyzyw) +
(xyywzyw) +
(zwxyzy) +
(zwxyzyw) +
(zwxzwxz))

É 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 = (((wxy + xyy + zwx) (w + x + y + z)* (xyz + xzw + ywz) (w + x + y + z)* (wxz + yzy + zyw)) +
((wxywz + wxyz + xyywz + zwxyz + zwxzw) (w + x + y + z)* (wxz + yzy + zyw)) +
((wxy + xyy + zwx) (w + x + y + z)* (xyzy + xyzyw + xzwxz + ywzyw)) +
(wxywzyw + wxyzy + wxyzyw + xyywzyw + zwxyzy + zwxyzyw + zwxzwxz))