The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.6k 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?

  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.
asked in Theory of Computation by Veteran (355k points)
edited by | 2.6k views
+2
to be more precise , L2 is dcfl   and dcfl is closed under compliment ,     so  it will recursive trivially   and option c is correct
0

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.

0
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 ?
0

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. 

2 Answers

+30 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).

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

In official key, answer is D only:

http://gatecse.in/w/images/1/1e/Key_CS_2013.pdf

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

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

+2
Sorry. It is DCFL.
0
why intersection of regular language with CFL a CFL??
+1
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.
http://cs.stackexchange.com/questions/18642/intersection-of-context-free-with-regular-languages
0
Complement of DCFL is nt CSL ? Every CSL is also Recursive hence we say complement of DCFL is Recursive . Correct me if wrong
+7
Complement of DCFL is DCFL and hence CFL and hence CSL and hence REC and hence R.E. also.
0
@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?
+2
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.
0
yes i also want to know the PDA only...
0
@Arjun Suresh Sir, How can we prove that complement of Context Free Language is Recursive?
+1
@Anchit How to prove complement of recursive is recursive?
0
Complement the corresponding DFA. We still get regular language
+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

answered by Boss (30.7k points)
0

"complement of a CFL is recursive .."

from where does this theorem come .. ?
 

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


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

38,174 questions
45,676 answers
132,609 comments
49,563 users