GATE CSE 2020 | Push Down Automata and Context Free Language Question 11 | Theory of Computation

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

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

GATE CSE 2009

MCQ (Single Correct Answer)

-0.3

Which one of the following is FALSE?

There is a unique minimal $$DFA$$ for every regular language

Every $$NFA$$ can be converted to an equivalent $$PDA$$

Complement of every context free language is recursive

Every non deterministic $$PDA$$ can be converted to an equivalent deterministic $$PDA$$