Ace Test Series: Theory Of Computation - Finite Automata

Question

Simple question. However the question mention MFA or minimal Finite Automation. So can i take NFA as it has 3 states. DFA has four ( 1 extra for the dead state);

Comments

You are right. It is a trend in ACE questions, that whenever they ask MFA, they consider DFA by default!!

Answer 1

L1$\cap$L2={ \epsilon$ , ab}

To construct DFA for above language we need 4 states including 1 trap state.

Comments

As the language contains only Ɛ and 'ab' , I construct a DFA having 3 states. Would you explain how do you get 4 state DFA.

Answer 2

Well it's quite simple.

Answer 3

Minimal FA is always NFA, and for Minimal FA is always NFA, and for the given question 3 is correct. the given question 3 is correct.

if NFA has 'n' states, then equivalent DFA will always have a number of states greater than n and lesser than 2ⁿ. Hence minimal FA is always NFA.