Theory of Computation
Q243.
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L (M) be the language accepted by a Turning machine M. Which of the following decision problems are undecidable ? I. Given a regular expression R and a string w, is w\in L(R)? II. Given a context-free grammar G, L(G)=\phi? III. Given a context-free grammar G, is L(G)=\Sigma* for some alphabet \Sigma? IV. Given a Turning machine M and a string w, is w\inL(M)?Q245.
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = \Phi? 2. G is a CFG. Is L(G) = \Sigma ^{*} ? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?Q246.
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?Q247.
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is true?Q248.
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet {0, 1}. S2: Set of all syntactically valid C programs. S3: Set of all languages over the alphabet {0, 1}. S4: Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?Q250.
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi? II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = \phi?