Let <M> be the encoding of a Turing machine as a string over ∑= {0, 1}. Let L = { <M> |M is a Turing machine that accepts a string of length 2014 }. Then, L is

Related MCQs

• Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
• The grammar whose productions are <stmt> → if id then <stmt> <stmt> → if id then <stmt> else <stmt> <stmt> → id := id is ambiguous because a) the sentence if a then if b then c:= d has two parse trees b) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse trees c) the sentence if a then if b then c:= d else c:= f has more than two parse trees d) the sentence if a then if b then c:= d else c:= f has two parse trees
• If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?
• Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
• For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
• Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
• Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
• For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
• Consider the following decision problems: (P1) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true?
• A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. T1: a?(b∣c)*a T2: b?(a∣c)*b T3: c?(b∣a)*c Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs?