Finite automata

Question

The number of DFA with four states that can be constructed  over alphabet {a,b} with designated initial state are 2^n then value of n is .....

Comments

20?

---

Yes please explain

Answer 1

What we know:

Its a DFA hence for each symbol in the alphabet goes to a single state.

There will be a single start state and multiple final states.

4 states on both the symbols of alphabet can go to one of the four states, states^{states*symbols}=4^4*2

We know that the initial state is known.

Any of the four states can be final state, hence 2⁴

So in total 2⁴*4^4*2=2⁴.2^2*4*2=2²⁰

We are said 2ⁿ number of DFAs and asked value of n. So, the value of n is 20. :-)

If you didnt understand the see the following

Consider the following transition table

	a	b
--->W	W or X or Y or Z	W or X or Y or Z
X	W or X or Y or Z	W or X or Y or Z
Y	W or X or Y or Z	W or X or Y or Z
Z	W or X or Y or Z	W or X or Y or Z

We are said that there is a designated Start state lets say the designated start state is "W"(if that was not said then we would have multiplied by 4)

There are |states| * |symbols| cells and each may have one of the 4 states, this is how we get 4^4*2

And a state can be final or non final hence we multiply it by 2⁴.

Comments

Ok so let me get this straight ok:-

If there are 4 states then any of the possible subset of these states can be the final states hence = 2^4

Now from one state on a symbol there can be 4 possible transitions i.e. its like we are defining a function from state {Q1,Q2,Q3,Q4}-->{Q1,Q2,Q3,Q4}, So total function be 4^(4*2) as there are 2 symbols so 4 ^ 8.

So total DFA = 2^4 * 4^8 = 2^20 ?

Now say had the start state not be designated then the answer should be 4 * 2^20 ie. 2^22 right ?

---

Perfect!

1) Now tell me 2 state DFA, designated initial state, symbols a and b

DFA  accepts L={} whwhi means accepts nothing. Answer:20

2) two state dfa over a and v, designated inutual state that accepts everything. ANS:20

---

I am not getting 20 Can u explain it please

---

For the first question

divide it into 4 cases

Lets say A and B are two states

1) A is final B is final

2) A is non final B is final

3) A is final B is non final

4) A is non final B is non final

If we see case 1 and 3, they make initial state as final, which makes the dfa accept epsilon but we dont want anything to be accepted.

So now procced with case 2 and 4, make sure  in case 2 from state A there should be no transition to state B since B is final.

Case 4 is 16 and case 2 is 4

So total 20

Answer 2

Number of ways to select initial state = 1 // Given that initial state is designated

Number of possibilities for final state = 2⁴          // Any subset of the given states can be final state

Number of possible transitions = Number of functions from Σ{a,b} Χ 4 -----> 4     = 4⁸    // 4 is the number of states

Total number of DFA = 2⁴ * 4⁸ = 2²⁰