Question

what is the number of states required in minimal dfa to accept the string of a regular language that contain 2 a's and 3 b's over the input alphabet {a,b}

Answer 1

Subjects to be Learned

Language accepted by DFA

Contents

Here we are going to formally define what is meant by a DFA (deterministic finite automaton) accepting a string or a language.

A string w is accepted by a DFA < Q , , q0 , , A > , if and only if *( q0 , w ) A . That is a string is accepted by a DFA if and only if the DFA starting at the initial state ends in an accepting state after reading the string.

A language L is accepted by a DFA < Q , , q0 , , A > , if and only if L = { w | *( q0 , w ) A } . That is, the language accepted by a DFA is the set of strings accepted by the DFA.

Example 1 :

This DFA accepts {} because it can go from the initial state to the accepting state (also theinitial state) without reading any symbol of the alphabet i.e. by reading an empty string . It accepts nothing else because any non-empty symbol would take it to state 1, which is not an accepting state, and it stays there.