Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.(a) N^2(b) 2^N(c) 2N(d) N!This question was addressed to me during an online exam.My question is taken from Finite Automata and Regular Expressions topic in division Compiler Introduction of Compiler

Given a NFA with N states, the maximum number of states in an equivale

1.	Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.(a) N^2(b) 2^N(c) 2N(d) N!This question was addressed to me during an online exam.My question is taken from Finite Automata and Regular Expressions topic in division Compiler Introduction of Compiler
Answer» Right choice is (b) 2^N To explain: The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must FOLLOW EITHER the arrow from state 1 to 2, or from state 3 to 4. ALSO, NEITHER state 2 nor 4 have OUTGOING ε-moves.

Discussion

No Comment Found

Related InterviewSolutions

If A, B and C are any three sets, then A × (B ∪ C) is equal to _____________(a) (A × B) ∪ (A × C)(b) (A × B) ∩ (A × C)(c) (A ∪ B) × (A ∪ C)(d) None of the mentionedI had been asked this question by my school teacher while I was bunking the class.Asked question is from Relations topic in section Compiler Introduction of Compiler
If A, B and C are any three sets, then A – (B ∪ C) is equal to _____________(a) (A – B) ∪ (A – C)(b) (A – B) ∪ C(c) (A – B) ∩ (A – C)(d) (A – B) ∩ CI have been asked this question in semester exam.The above asked question is from Relations in chapter Compiler Introduction of Compiler
If A ∩ B = B, then?(a) A ⊂ B(b) A = ø(c) B ⊂ A(d) B = øThe question was posed to me in examination.I would like to ask this question from Relations in section Compiler Introduction of Compiler
If every aRb and bRc implies aRc, then the relation is transitive.(a) True(b) FalseI had been asked this question in an online interview.My question is from Relations in section Compiler Introduction of Compiler
The RE in which any number of 0′s is followed by any number of 1′s followed by any number of 2′s is?(a) (0+1+2)*(b) 0*1*2*(c) 0* + 1 + 2(d) (0+1)*2*This question was addressed to me by my college professor while I was bunking the class.The above asked question is from Regular Expression in portion Compiler Introduction of Compiler
The regular expressions denote zero or more instances of an x or y is?(a) (x+y)(b) (x+y)*(c) (x* + y)(d) (xy)*I had been asked this question in a job interview.The origin of the question is Finite Automata and Regular Expressions topic in division Compiler Introduction of Compiler
The regular expression denotes a language comprising all possible strings of even length over the alphabet (0, 1).(a) 1 + 0(1+0)*(b) (0+1) (1+0)*(c) (1+0)(d) (00+0111+10)*I have been asked this question at a job interview.Origin of the question is Regular Expression in chapter Compiler Introduction of Compiler
Parsing is also known as ________(a) Lexical Analysis(b) Syntax Analysis(c) Semantic Analysis(d) Code GenerationThe question was posed to me during an interview.I need to ask this question from Lexical Analysis in section Compiler Introduction of Compiler
The lexical analyzer takes _________ as input and produces a stream of _______ as output.(a) Source program, tokens(b) Token, source program(c) Either of the two(d) None of the mentionedThis question was addressed to me in homework.The query is from Lexical Analysis topic in division Compiler Introduction of Compiler
Regular Expressions can be used with XML checkpoints.(a) True(b) FalseThe question was asked in quiz.Question is from Finite Automata and Regular Expressions in section Compiler Introduction of Compiler

Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.(a) N^2(b) 2^N(c) 2N(d) N!This question was addressed to me during an online exam.My question is taken from Finite Automata and Regular Expressions topic in division Compiler Introduction of Compiler

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment