+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 | 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
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)
Answer:

+9 votes
2 answers
1
+8 votes
2 answers
2
+3 votes
1 answer
3