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?

Related MCQs

• 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
• 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
• 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?
• 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?
• 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?
• 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? 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
• Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
• Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?