The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.5k 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 (326k points) | 1.5k 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 ?

2 Answers

+19 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 (326k points)
selected by
yeah sir explanation is right ...means the ofcl ans key is wrong.

In official key, answer is D only:

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

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.
http://cs.stackexchange.com/questions/18642/intersection-of-context-free-with-regular-languages
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
+5 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 (29.7k points)


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

28,946 questions
36,792 answers
91,068 comments
34,689 users