The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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 ?

if in stack only one comparison required can we say it is dcfl ?

+34 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.

0

DPDA of L2 like this...push all 0's in stack first when 1 comes skipped all 1's after every 0 pop 1........in last

two cases happened

p>r...means no. of 0's grater than 1's( means stack still contain some 0's)

p<r...means no. of 0's less than no. of 1's( when stack will be empty then go to direct final state)

I think this logic help to draw DPDA.

two cases happened

p>r...means no. of 0's grater than 1's( means stack still contain some 0's)

p<r...means no. of 0's less than no. of 1's( when stack will be empty then go to direct final state)

I think this logic help to draw DPDA.

+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.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users