The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
Consider the following languages

$L_1$ = $\{a^nb^n\mid 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
asked in Theory of Computation by Veteran (14.6k points)
retagged by | 162 views

1 Answer

+4 votes
Best answer
$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_2$ , 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 final state from where the PDA accepts any string. Otherwise, at the end of the string, if stack is non-empty, accept the string and if stack is empty, reject the string.
answered by Veteran (332k points)
selected by

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,732 questions
39,308 answers
36,731 users