Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Related MCQs

• 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?
• 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?
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L’ (complement of L) also context-free? 3) If L is a regular language, then is L’ also regular? 4) If L is a recursive language, then, is L’ also recursive?
• If L and L' are recursively enumerable, then L is
• 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?
• Which of the following are decidable ? 1. whether the intersection of two regular language is infinite. 2. whether a give context free language is regular 3. whether two push down automata accept the same language. 4. whether a given grammar is context free
• 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?
• 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?
• Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free
• Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?