Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

Related MCQs

• Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
• 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 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 minimum state automaton equivalent to the above FSA has the following number of states
• 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?
• 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 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 following statements related to compiler construction : I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata. II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct?
• Consider the following expression grammar. The seman-tic rules for expression calculation are stated next to each grammar production. E → number E.val = number. val | E '+' E E(1).val = E(2).val + E(3).val | E '×' E E(1).val = E(2).val × E(3).val The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
• Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is: