Let \(Ξ£=π,π\) and language \(πΏ=ππ,ππ\). Then, the complement of \(πΏ\) is
2016
LetΒ \(Ξ£=π,π\)Β and languageΒ \(πΏ=ππ,ππ\). Then, the complement ofΒ \(πΏ\)Β is
- A.
\(\left\{\lambda, a, b, ab, ba \right\} \cup \left\{w \in\left\{a, b\right\}^{*} | |w| > 3 \right\}\) - B.
\(\left\{a, b, ab, ba \right\} \cup \left\{w \in \left\{a, b\right\}^{*} | |w| \geq 3 \right\}\) - C.
\(\left\{w \in \left\{a, b\right\}^{*} | |w| > 3\right\} \cup \left\{a, b, ab, ba \right\}\) - D.
\(\left\{\lambda, a, b, ab, ba\right\} \cup \left\{w \in \left\{a, b\right\}^{*} | |w| \geq 3 \right\}\)
Attempted by 343 students.
Show answer & explanation
Correct answer: D
Answer: The complement of the language consists of all strings over {a,b} except the two strings aa and bb.
Start from Ξ£* = all strings over {a,b}, which includes the empty string Ξ», length-1 strings {a,b}, length-2 strings {aa,ab,ba,bb}, and all strings of length β₯ 3.
Given L = {aa, bb}, the complement is Ξ£* \ {aa, bb} = { w β {a,b}* | w β aa and w β bb }.
Equivalently, list what remains explicitly: {Ξ», a, b, ab, ba} βͺ { w β {a,b}* | |w| β₯ 3 }.
Common mistakes to avoid: using { w | |w| > 3 } wrongly omits length-3 strings, and omitting Ξ» leaves out the empty string.
Therefore the correct description of the complement is {Ξ», a, b, ab, ba} βͺ { w β {a,b}* | |w| β₯ 3 } (equivalently { w β {a,b}* | w β aa and w β bb }).
A video solution is available for this question β log in and enroll to watch it.