(7 intermediate revisions by the same user not shown)
Line 15: Line 15:
 
(D) None of the above
 
(D) None of the above
  
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
   $L_1$ is clearly a DCFL. And DCFL is closed under complement. Hence, $L_2$ is also DCFL.
 
   $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ⁿ}.
+
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
+
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.
 +
 
 +
{{Template:FBD}}
 +
 
 +
[[Category: Non-GATE Questions from Automata Theory]]

Latest revision as of 11:25, 15 July 2014

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

Solution by Arjun Suresh

 $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 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.




blog comments powered by Disqus

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

Solution[edit]

 $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ⁿ}. 

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