The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is

Related MCQs

• Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S --> aB S --> bA B --> b A --> a B --> bS A --> aS B --> aBB A --> bAA Which of the following strings is generated by the grammar?
• S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of
• Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
• 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)*?
• 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?
• 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?
• 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
• 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?
• 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
• 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?