The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 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**?

- $L_2$ is context-free.
- $L_1\cap L_2$ is context-free.
- Complement of $L_2$ is recursive.
- Complement of $L_1$ is context-free but not regular.

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

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

+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

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

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.

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.

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,532 answers

146,046 comments

62,298 users