2.7k 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.
edited | 2.7k 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)

### 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.

$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).

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

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.

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.