Test: Pushdown Automata: CFL & DCFL- 1 - Computer Science Engineering (CSE) MCQ

 cannot be accepted by the deterministic PDA since guessing of the alphabet after which reversal is done is required. One must have to guess the end of w, so that start of w^R is found. The word cannot be determined deterministically as w ∈ (0 + 1)* which includes multiple combinations.

According to the closure properties regular language is closed under union, intersection, Kleen closure, concatenation, complementation. But the complementation of any language need not to be always regular.

According to closure properties regular languages are closed under the ail finite basic operations like:  
But CFL is closed only under 
Also Regular inter section of CFL i.e. CFL intersected with regular language.

Regular and context free languages are both closed under union and concatenation while only regular is closed under intersection.

In L₁ only one stack is required since only one comparison is there. While for L₂ and L₃ two stacks are required since there are 2 comparisons. So, only L₁ is context free language as it is accepted by PDA.

Since L₁ and L₂ are regular and context free languages respectively CFL are closed under regular ∪, ∩, therefore
(a) L₁ ∪ L₂ is CFL and therefore regular too.
(b) L₁ ∩ L₂ is not regular
(c) L₁ * is regular

Out of the four operations given, as per the closure properties CFL are closed under only union.

Here for the languages (i) and (ii) we can design a PDA Hence they are CFL.
In (iii) and (iv) we cannot conclude whether number of (a) = number of (c) and number of (b) = number of (d) using only one stack memory so they aren’t CFL.

Since the power of recognization of NFA is less then the PDA. Also CFL can be recognized by the one which has equal or higher power than the PDA. Both PDA and LBA can recognize the CFL.