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))