The Gateway to Computer Science Excellence
+25 votes

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?

  1. $L_2$ is context-free.
  2. $L_1\cap L_2$ is context-free.
  3. Complement of $L_2$ is recursive.
  4. Complement of $L_1$ is context-free but not regular.
in Theory of Computation by Veteran (422k points)
edited by | 3.7k views
to be more precise , L2 is dcfl   and dcfl is closed under compliment ,     so  it will recursive trivially   and option c is correct

In option b) 

Can we say L1 ∩ L2 = 0*1* (as both have p,q variables independent) 

and 0*1* is indeed Regular and hence it's CFL.

how to identify whether given language is accepted by dcfl or cfl

if in stack only one comparison required can we say it is dcfl ?

Anyone, please make PDA of L2. is it not a case that we need 2 stacks to make it, because there are many possibilities L2 can be{01,10,000,0100,00110,0010.......} and we have to compare that P≠R. 

Cfl are not closed under complementation.

3 Answers

+37 votes
Best answer

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

$L_2$ 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, $L_1 \cap L_2$ is context-free as regular $\cap$ context-free is context-free. $\rightarrow$ (B) is true.

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

by Veteran (422k points)
edited by
yeah sir explanation is right ...means the ofcl ans key is wrong.

In official key, answer is D only:

sir, can u pls show me the PDA for L2 ?

Why L2 is not DCFL?? (q> 0 ∪ 0+ )

Sorry. It is DCFL.
why intersection of regular language with CFL a CFL??
Because given a PDA and an autmata we can make a new PDA which would accept the intersection of the corresponding CFL and RL. This construction should be in TOC text.
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...
@Arjun Suresh Sir, How can we prove that complement of Context Free Language is Recursive?
@Anchit How to prove complement of recursive is recursive?
Complement the corresponding DFA. We still get regular language
@arjun sir

can we also say complement of CFL is CSL???? or only recursive ??
can anybody make the DPDA for language L2 and post in the comment thanks in advance
DPDA of L2 like this...push all 0's in stack first when 1 comes  skipped all 1's after every 0 pop last

two cases happened

p>r...means   no. of 0's grater than 1's( means stack still contain some 0's)

p<r...means no. of 0's less than no. of 1's( when stack will be empty then go to direct final state)

 I think this logic help to draw DPDA.

p and r for number of 0's. How come we are comparing no of 0's and no of 1's in the pda ? @VIDYADHAR SHELKE 1

+8 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

by Boss (30.6k points)

"complement of a CFL is recursive .."

from where does this theorem come .. ?

complement is not closed under CFL. but complement is closed under Recursive. Every CFL is also Recursive hence complement of a CFL is Recursive.
0 votes

A) L2 is CFL. Hence statement is true.

B) Here L1 is regular language and L2 is CFL. CFL is closed under the intersection with regular language as (RLCFL) is also context free. Hence (L1L2) is context free. Hence statement is true.

C) Complement of L2 is recursive. Complement of CFL is always context sensitive. Hence statement is true.

D) L1 is regular language, RL are closed under complement operation. Hence, complement of L1 is also regular, statement is false.

hence, option D is correct.

by (301 points)

Related questions

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
50,666 questions
56,154 answers
93,718 users