GATE CSE 2011 | Question: 26

Question

Consider the languages $L1, \:L2 \:and \: L3$ as given below.

$L1=\{0^p 1^q \mid p, q \in N\}, \\ L2 = \{0^p 1^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{0^p 1^q 0^r \mid p, q, r \in N\: and \: p=q=r\}.$ 

Which of the following statements is NOT TRUE?

• A. Push Down Automata (PDA) can be used to recognize $L1$ and $L2$
• B. $L1$ is a regular language
• C. All the three languages are context free
• D. Turing machines can be used to recognize all the languages

Comments

question miss print in go pdf

---

>1 linear comparisons required in L3
Hence it is not CFL

Answer 1

Answer is C.

$L_{1}$ is RL

$L_{2}$ is CFL

$L_{3}$ is CSL

Turning Machine is powerful Machine.  It can be used to accept all the languages  (RL, CFL, CSL, RE)

Comments

Ya we can say ...

---

@Brij Mohan Guptaamong following option all the parts are not belonging to same language.But in option they have given all languages as context free which is wrong!.so opt c is correct.

 

---

Sir, answer should be D because you already given brief knowledge about question, by which we can say answer should be D

Answer 2

L1 is Regular(no stack is required,it has a DFA) so obviously it is CFL

L2 requires one stack so it is CFL

L3 more than one stack is required-CSL

And every RL,CFL,CSL are Recursively Enumerable so accepted by TMs.

So C is answer

Comments

Then, D will be the answer.

Answer 3

c is the right answer...... as L3 is not CFL.....L3 is CSl

Answer 4

L_{1 = Regular because we can give a REGEX: 0⁺1⁺}

L_{2 = equal number of 0's and equal number of 1's and after a "1" you can never see a "0"}

Take a valid string from L2 = "0011"

Push all "0's"and for every "1" pop one "0" Hence it's DCFL because we know when and what to Push and Pop and every DCFL is CFL.

L₃ = {0^p1^p0^p | p>0, p=q=r} and this is classic CSL.

p>0 because we have given p=q=r therefore I can write it as "p" in place of q and r and since p,q,r belongs to N (Natural Number) which makes p>0

Hence Answer is c) because L1 = L2 = CFL, but L3 = CSL, not CFL

Answer 5

The statement that is NOT TRUE is C.

Here is a step-by-step analysis of each language and statement.

---

 

Language Analysis

 

• $L1 = \{0^p 1^q \mid p, q \in N\}$

  This language consists of zero or more 0s followed by zero or more 1s. The number of 0s ($p$) and 1s ($q$) are independent. This language is described by the regular expression 0*1*.

  • Conclusion: $L1$ is a regular language.

• $L2 = \{0^p 1^q \mid p, q \in N \text{ and } p = q\}$

  This is the language $\{0^p 1^p \mid p \ge 0\}$. This is the classic example of a language that is not regular but is context-free. It requires a pushdown automaton (with a stack) to push a symbol for each 0 and pop a symbol for each 1 to ensure the counts are equal.

• $L3 = \{0^p 1^q 0^r \mid p, q, r \in N \text{ and } p = q = r\}$

  This is the language $\{0^p 1^p 0^p \mid p \ge 0\}$. This language is not context-free. A single stack cannot perform the two required comparisons (matching the 0s to the 1s and matching the 1s to the second set of 0s). This is a context-sensitive language.

---

 

Evaluation of Statements

 

• A. Push Down Automata (PDA) can be used to recognize $L1$ and $L2$

  • $L1$ is regular, and all regular languages are also context-free. Therefore, a PDA can recognize $L1$.

  • $L2$ is a context-free language. By definition, a PDA can recognize it.

  • This statement is TRUE.

• B. $L1$ is a regular language

  • As determined above, $L1$ is described by 0*1*.

  • This statement is TRUE.

• C. All the three languages are context free

  • $L1$ is context-free.

  • $L2$ is context-free.

  • $L3$ is not context-free.

  • Since $L3$ is not context-free, this statement is FALSE.

• D. Turing machines can be used to recognize all the languages

  • All regular, context-free, and context-sensitive languages are recursive (decidable). A Turing machine can decide (and therefore recognize) all recursive languages.

  • $L1$, $L2$, and $L3$ are all recursive.

  • This statement is TRUE.

Answer 6

• Analyze $L_1$:

  • $L_1 = \{0^p 1^q \mid p, q \in \mathbb{N}\} = 0^* 1^*$

  • Has no dependency between $p$ and $q$.

  • It is a Regular Language (and therefore also a CFL).

• Analyze $L_2$:

  • $L_2 = \{0^p 1^q \mid p, q \in \mathbb{N} \text{ and } p = q\} = \{0^n 1^n \mid n \ge 0\}$

  • Requires matching one count ($p = q$), which a single stack Pushdown Automaton (PDA) can do.

  • It is a Context-Free Language (CFL) (specifically a DCFL), but not regular.

• Analyze $L_3$:

  • $L_3 = \{0^p 1^q 0^r \mid p, q, r \in \mathbb{N} \text{ and } p = q = r\} = \{0^n 1^n 0^n \mid n \ge 0\}$

  • Requires matching three independent counts simultaneously, which cannot be handled by a single PDA stack (provable by the Pumping Lemma for CFLs).

  • It is a Context-Sensitive Language (CSL), NOT a Context-Free Language.

Now,

• A. Push Down Automata (PDA) can be used to recognize $L_1$ and $L_2$: TRUE (every regular language and context-free language is recognized by a PDA).

• B. $L_1$ is a regular language: TRUE (matches the regular expression $0^* 1^*$).

• C. All the three languages are context free: FALSE ($L_3$ is not context-free).

• D. Turing machines can be used to recognize all the languages: TRUE (all three are decidable/recursive languages).