GATE CSE 2022 | Push Down Automata and Context Free Language Question 5 | Theory of Computation

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Consider the following languages:

L₁ = {aⁿ waⁿ | w $$\in$$ {a, b}*}

L₂ = {wxw^R | w, x $$\in$$ {a, b}*, | w | , | x | > 0}

Note that w^R is the reversal of the string w. Which of the following is/are TRUE?

L₁ and L₂ are regular.

L₁ and L₂ are context-free

L₁ is regular and L₂ is context-free.

L₁ and L₂ are context-free but not regular.

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Consider the following languages:

$$\eqalign{ & {L_1} = \{ ww|w \in \{ a,b\} *\} \cr & {L_2} = \{ {a^n}{b^n}{c^m}|m,\,n \ge 0\} \cr & {L_3} = \{ {a^m}{b^n}{c^n}|m,\,n \ge 0\} \cr} $$

Which of the following statements is/are FALSE?

L₁ is not context-free but L₂ and L₂ are deterministic context-free.

Neither L₁ nor L₂ is context-free.

L₂, L₃ and L₂ $$\cap$$ L₃ all are context-free.

Neither L₁ nor its complement is context-free.

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

Consider the language
L = { $${a^n}|n \ge 0$$ } $$ \cup $$ { $${a^n}{b^n}|n \ge 0$$ }
and the following statements.

I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

I only

II only

I and III only

III only

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.3

Which of the following languages is generated by the given grammar? $$$S \to aS|bS|\varepsilon $$$

$$\left\{ {{a^n}{b^m}|n,m \ge 0} \right\}$$

$$\left\{ {w \in \left\{ {a,b} \right\}{}^ * |w} \right.$$ has equal number of $$a’s$$ and $$\left. {b's} \right\}$$

$$\left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{b^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$

$${\left\{ {a,b} \right\}^ * }$$