Finite Automata

Question

What is the minimum number of states it takes a Finite Automata to accept a string whose nth bit from RHS is 1 over {0, 1}*?

Comments

in case of NFA it will be 'n+1'

---

When we talk about Finite Automata it is considered to be NFA.

Answer 1

This is a standard FA design..

When we say FA , it is taken to be as an NFA..

So for nth bit from the right to be '1' , no of states in minimal NFA = n + 1

As far as number of states in minimal DFA is concerned , it is 2ⁿ..

One question came on the same topic this yr and I did a mistake ; wrote the number of states considering NFA while the question asked about minimal DFA..

Comments

In the question will it be specified DFA?

But, if we talk about FA it is always taken NFA, right?

---

Yes by default FA should be taken as NFA ..Some questions came like that in prev yrs also.