GATE IT 2008 | Question: 33

Question

Consider the following languages.

• $L_1 = \{a^i b^j c^k \mid i = j, k \geq 1\}$
• $L_2 = \{a^i b^j \mid j = 2i, i \geq 0\}$

Which of the following is true?

• A. $L_1$ is not a CFL but $L_2$ is
• B. $L_1 \cap L_2 = \varnothing $ and $L_1$ is non-regular
• C. $L_1 \cup L_2$ is not a CFL but $L_2$ is
• D. There is a $4$-state PDA that accepts $L_1$, but there is no DPDA that accepts $L_2$.

Comments

 shouldn’t $L_1 \cap L_2 = \epsilon $ instead of $\varnothing$
@Abhrajyoti00 

---

@JAINchiNMay It will be $\varnothing$ because L1 and L2 are disjoint sets. They don’t even have null string in common. See: L1 ends with ‘c’ and L2 does not. Also i=j and j=2i can never intersect. 

Answer 1

Both the languages can be accepted by a DPDA:

$L_1 =$ start pushing element $X$ into the stack on input '$a$' ... start to pop  $X$ on input '$b$' ... move to final state when stack empty and input  = '$c$'

$L_2 =$ start pushing elements $XX$ into the stack on input '$a$' ... start to pop  $X$ on input '$b$' ... move to final state when stack empty and input  = 'epsilon'

So, (A) and (D) are False.

$L_1 \cup L_2$ is a CFL ... we can build it by having $L_1, L_2$ and an extra state ... and an 'epsilon' transition to both $L_1$ and $L_2$ from that extra state.

So, (C) is false.

$L_1 \cap L_2 =$ Phi because we have no string $a^ib^j$ where $i=j$ and $i=2j$ for $i,j \geq1$

and clearly $L_1$ is not a regular language

So, (B) is true.

Comments

not closed means that the result of union operation  may or may not be DCFL so c is false.So option c can be true but not in all cases. in the case given in question it is not true.

---

@Satbir

when we say PDA by default we mean an NPDA.right?

and when we say turing machine by default we mean DTM.right?

---

Minor Correction @Danish,

In your answer in the end you've written  - > i=2*j

Instead of  - > j=2*i (which is given in the question)

Answer 2

the grammar for L2 will be  S → aSbb | ϵ

the grammar for L1 will be  S → S1C , S1 → aS1b | ϵ , C → cC | c

so both are CFL. and L1 is not regular as we cannot have finite automata which gives same no of b’s as a’s.