LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
A Boolean value
|
|
|
A state
|
|
|
A set of states
|
|
|
An edge
|
Detailed explanation-1: -In a DFA, the transition function always returns a single state; in an NFA, the transition function returns a set of states, which could be empty, or all of Q, or anything in between. ∗(r, x) if w = ax.
Detailed explanation-2: -3. What is the transitional function of an NFA? Explanation: Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q.
Detailed explanation-3: -As per the definition of DFA, so as NFA it can have only one initial state.
Detailed explanation-4: -True, Every NFA with more than one final state can be converted into an NFA with a single final state. Add a new state to the NFA and introduce epsilon transitions from every old final state to the new state.
Detailed explanation-5: -Formal Definition of an NDFA ∑ is a finite set of symbols called the alphabets. is the transition function where : Q × ∑ → 2Q. (Here the power set of Q (2Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)