List of top Computer Science & Information Technology Questions on Theory of Computations asked in TS PGECET

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