GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
1.2k views

Consider the following languages.

$L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0 \right \}$

$L_2 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0, p\neq r \right \}$

Which one of the following statements is FALSE?

(A) $L_2$ is context-free.
(B) $L_1∩ L_2$ is context-free.
(C) Complement of $L_2$ is recursive.
(D) Complement of $L_1$ is context-free but not regular.

asked in Theory of Computation by Veteran (294k points)   | 1.2k views
to be more precise , L2 is dcfl   and dcfl is closed under compliment ,     so  it will recursive trivially   and option c is correct

2 Answers

+16 votes
Best answer

L1 is regular and hence context-free also. Regular expression for L1 is 0*1*0*. So, (D) is the false choice. 

L2 is context-free but not regular.  We need a stack to count if the number of 0's before and after the 1 (1 may be absent also) are not same. So, L1 ∩ L2 is context-free as regular ∩ context-free is context-free. -> (B) is true.

Complement of L2 is recursive as context-free complement is always recursive (actually even context-sensitive).

 
answered by Veteran (294k points)  
selected by
Complement of DCFL is nt CSL ? Every CSL is also Recursive hence we say complement of DCFL is Recursive . Correct me if wrong
Complement of DCFL is DCFL and hence CFL and hence CSL and hence REC and hence R.E. also.
@Arjun sir can you please explain how push and pop operations are done here for PDA of L2? i tried but i failed to understand that... i understand that there is only 1 comparision in L2 so it is DCFL as well as CFL but how the PDA operations are done?
To show that L2 is a CFL, one can make use of grammar for L2

S --> 0S0 | AC | CB

A --> 0A | 0                     (for p>r)

B --> B0 | 0                     (for p<r)

C --> 1C | 1

Since the LHS of above equations consist of a single non-terminal, the grammar is context free

I am unable to translate this into a PDA, any help will be appreciated.
yes i also want to know the PDA only...
+3 votes

for $L_1$ we can see that $p, q, r$ are independent of each other $\therefore$ the language is Regular.

for $L_2$ we can see that only one comparison is there which is between $p$ and $r$. variable $q$ is independent of the two. Hence it can be seen that it is DCFL.

$A$ : saying $L_2$ is CFL is True.

$B$ : intersection of a CFL with Regular is closed $\therefore$ this option is True.

$C$ : the complement of any CFL is Recursive, since recursive languages are closed under complement and all CFLs are R. $\therefore$ this option is True

$D$ : Regular languages are closed under complement Hence, this option is FALSE.

answer = option D

answered by Veteran (28.7k points)  


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2076 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,649 answers
79,695 comments
31,069 users