The Gateway to Computer Science Excellence

+25 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 ?

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

0

p and r for number of 0's. How come we are comparing no of 0's and no of 1's in the pda ? @VIDYADHAR SHELKE 1

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

0 votes

A) *L*2 is CFL. Hence statement is true.

B) Here L1 is regular language and L2 is CFL. CFL is closed under the intersection with regular language as (RL*∩*CFL) is also context free. Hence (L1*∩*L2) is context free. Hence statement is true.

C) Complement of L2 is recursive. Complement of CFL is always context sensitive. Hence statement is true.

D) L1 is regular language, RL are closed under complement operation. Hence, complement of L1 is also regular, statement is false.

hence, option D is correct.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,154 answers

193,757 comments

93,718 users