GATE CSE 2021 Set 1 | Push Down Automata and Context Free Language Question 9 | Theory of Computation

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.33

Suppose that L₁ is a regular and L₂ is a context-free language, Which one of the following languages is NOT necessarily context-free?

L₁ ⋅ L₂

L₁ ∪ L₂

L₁ ∩ L₂

L₁ - L₂

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0

Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = ∑*}

L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = Φ}

L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = Φ}

L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = ∑*}

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\}^ * }$$

GATE CSE 2011

MCQ (Single Correct Answer)

-0.3

The lexical analysis for a modern computer language such as java needs the power of which one of the following machine model in a necessary and sufficient sense?

Finite state automata

Deterministic pushdown automata

Non -deterministic pushdown automata

Turing machine

PREVIOUS NEXT