LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
making starting state as final state.
|
|
|
no trival method.
|
|
|
making final states non-final and non-final to final.
|
|
|
make final as a starting state.
|
Detailed explanation-1: -Right answer is (c) making final states non-final and non-final to final. Easiest explanation: String accepted in previous DFA will not be accepted and non accepting string will be accepted .
Detailed explanation-2: -If (Q, ∑, , q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa. So, RE = a+.
Detailed explanation-3: -The complement of a DFA is obtained by making the non-final states as final states and final states as non-final states. The language which is accepted by the complemented DFA L2 is the complement of language L1.
Detailed explanation-4: -In automata theory, complementation of a Büchi automaton is construction of another Büchi automaton that recognizes the complement of the -regular language recognized by the given Büchi automaton. Existence of algorithms for this construction proves that the set of -regular languages is closed under complementation.
Detailed explanation-5: -The normal way to take the complement of a regular language L, assuming you have a DFA recognising L is the following: Take all accept states and change them into non-accepting states, and vice versa.