1) S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of (A) All palindromes. (B) All odd length palindromes. (C) Strings that begin and end with the same symbol (D) All even length palindromes. Answer (B) The strings […]

1. Which of the following pairs have different expressive power? a) DFA AND NDFA b) DPDA AND NPDA c) Deterministic single tape turing machine and Non-Deterministic single tape turing machine d) single tape turing machine and multiple  tape turing machine ANSWER IS B DPDA cannot handle languages or grammars with ambiguity, but […]

1 Let R1 and R2 be regular sets defined over alphabet ∑ then (a.) R1 UNION R2 is regular (b.) R1 INTERSECTION R2 is regular (c.) ∑ INTERSECTION R2 IS NOT REGULAR (d.) R2* IS NOT REGULAR 2 Consider the production of the grammar S->AA A->aa A->bb Describe the language […]

(51) S -> a α b I b a c I ab S -> α S I b S -> α bb I ab S -> bdb I b The grammar described above is (A) Context free (B) Context sensitive (C) Regular (D) LR(k) ANSWER: Context sensitive   (52) Match […]

(41) The set which is not countable if we have ∑ = {a, b}, is (A) Set of all languages over ∑ accepted by turing machine (B) Set of all regular languages over ∑ (C) Set of all strings over ∑ (D) Set of all languages over ∑   ANSWER: […]

(21) State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = […]

(11) Which one of the following statement is true? (A) The intersection of two context free languages is context free (B) A context free language can always be accepted by a deterministic push down automaton (C) The union of two context free languages is context free (D) The complement of […]

(1) From the options given below, the pair having different expressive power is (A) Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA) (B) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA) (C) Single tape turning machine and multi tape turning machine. (D) Deterministic single tape turning machine […]

THEORY OF COMPUTATION EXCLUSIVE QUESTIONS THEORY OF COMPUTATION SET – 1 THEORY OF COMPUTATION SET – 2 THEORY OF COMPUTATION SET – 3 THEORY OF COMPUTATION SET – 4 THEORY OF COMPUTATION SET- 5 THEORY OF COMPUTATION SET- 6