List of top Computer Science & Information Technology Questions on Theory of Computations

The language \(L=\{0^n1^n2^n\mid n\ge0\}\) is a

The number of internal states of a Universal Turing Machine should be at least

Given a TM \(M\), a state \(q\), and input \(w\), determine whether computation of \(M\) on \(w\) ever visits state \(q\).

Which of the following regular expressions denote a language comprising all possible strings of even length over the alphabet \(\{0,1\}\)?

The following CFG generates strings of terminals that have

Which language can be accepted by a PDA but not by an FA?

Suppose a language \(L_1\) has 2 states and \(L_2\) has 2 states. After using the cross product construction method, we have a machine \(M\). The total number of states in \(M\) are

Which among the following cannot be accepted by a regular grammar?

The minimum number of productions required to produce a language consisting of palindrome strings over \(\Sigma=\{a,b\}\) is

The diagram given below refers to a non-deterministic finite state automaton that accepts the language having

Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

For $\Sigma = \{a,b\}$, let us consider the regular language $L = \{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k},\; k \ge 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$?