You do not have permission to edit this page, for the following reason:
You can view and copy the source of this page.
Templates used on this page:
Return to Automata qn 2.
Consider the following languages
$L_1 = \{a^nb^n| n \ge 0\}$
$L_2 =$ Complement($L_1$)
Chose the appropriate option regarding the languages $L_1$ and $L_2$
(A) $L_1$ and $L_2$ are context free
(B) $L_1$ is context free but $L_2$ is regular
(C) $L_1$ is context free and $L_2$ is context sensitive
(D) None of the above
$L_1$ is clearly a DCFL. And DCFL is closed under complement. Hence, $L_2$ is also DCFL.
We can make a PDA for L₂ , using the same PDA for {aⁿbⁿ} as follows:
Start by pushing each a on to stack. When b comes start popping. If 'a' comes after a 'b' or 'b' comes when the stack is empty, go to a new state from where the PDA accepts any string. (make it the final state and accepts everything else in the string). Otherwise, at the end of the string, if stack is non-empty, accept the string
GATECSE