Consider \(β=\{π€,π₯\}\) and \(π=\{π₯,π¦,π§\}\). Define homomorphism \(β\)β¦
2019
ConsiderΒ \(β=\{π€,π₯\}\)Β andΒ \(π=\{π₯,π¦,π§\}\). Define homomorphismΒ \(β\)Β by:
\(β(π₯)=π₯π§π¦ \\ β(π€)=π§π₯π¦π¦\)
IfΒ \(πΏ\)Β is the regular language denoted byΒ \(π=(π€+π₯^β)(π€π€)^β\), then the regular languageΒ \(β(πΏ)\)Β is given by
- A.
\((π§π₯π¦π¦+π₯π§π¦)(π§π₯π¦π¦) \) - B.
\((π§π₯π¦π¦+(π₯π§π¦)^β)(π§π₯π¦π¦π§π₯π¦π¦)^β \) - C.
\((π§π₯π¦π¦+π₯π§π¦)(π§π₯π¦π¦)^β \) - D.
\((π§π₯π¦π¦+(π₯π§π¦)^β)(π§π₯π¦π¦π§π₯π¦π¦)\)
Attempted by 50 students.
Show answer & explanation
Correct answer: B
Apply the homomorphism to each symbol: h(x)=xzy, h(w)=zxyy
Start from the given regular expression (w + x*)(ww)*.
Replace each occurrence of w by zxyy and each x by xzy.
Convert x* to (xzy)* and (ww)* to (zxyy zxyy)* because h(ww)=h(w)h(w)=zxyy zxyy.
Therefore h(L) = (zxyy + (xzy)^*)(zxyy zxyy)^*
A video solution is available for this question β log in and enroll to watch it.