in Theory of Computation
397 views
0 votes
0 votes
How many ‘n’ state FA are possible with ‘m’ symbols with –

(i) Designated initial state

(ii) With designated initial and final state

(iii) With no designated initial and final state

How can I approach this?
in Theory of Computation
by
397 views

2 Comments

@ankit3009 Can you help me with this?

1
1

https://youtu.be/VLB7xJE8fQ4

 

Watch this and you are never going to forget this concept ever.

4
4

1 Answer

7 votes
7 votes
Best answer
i. $2^{n}*n^{mn}$

ii.$n^{mn}$

iii.$2^{n}*n^{mn}*n$

$2^{n}$ → No designated final state.For each state we have two choice either final or non final.

n → No designated initial state.We have n choice for initial state.Any of the n states can           be initial state.
selected by

4 Comments

@ankit3009 Done(Favorite ). Not soo good trying to learn from gate overflow answer and comments. Thanks @gateoverflow.

1
1

@raja11sep Thanks for such descriptive comment, I got the approach I was just little confused why #ways for selecting initial state is ‘n’, I literally forgot that there can be only 1 initial state (such a silly mistake ik :p)

2
2
Yes this what DFA definition says. :)
2
2

Related questions