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?

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
• Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
• Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
• The minimum state automaton equivalent to the above FSA has the following number of states
• 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
• 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?
• 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?
• Let L={w \in (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
• A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
• Consider the grammar S → (S) | a Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good