# Theory of computation dfa construction

108 views
$\Large L = \left \{ a^{m^n} | n \geq 1, m > n \right \}$

What is the Minimum no.of states in a DFA which accept this language

edited
0

did you get what are the stings of L ?

if you get it, then 90% of your problem solved.

https://gateoverflow.in/242910/regular-grammar

here consider n=1 permanently and m=2,3,4,5,............ so it is set of all strings of length atleast 2....

selected by
0
Not length ...no.of a's precisely...dfa should have 3 states then?

## Related questions

1 vote
1
470 views
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.
2
592 views
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
3
1.1k views
Number of states for DFA which is divisble by 8 , I mostly try to identify by using number of distinct states. In this case , it would be 8 ; but minimized dfa would be less ? I read somewhere , the unique states sould be 4 and so minimum states are 4. Can't ... exceprt now , but is this right ? And can someone explain , what is meant by unique states ? Do we have fixed formula for such problems ?
1 vote
Let $q_0$ and $q_1$ be two states, with $q_0$ always being the initial state. Let the alphabet be $\{a, b\}$. Then, the possible number of DFA's with only these two states $q_0$ and $q_1$ is? 32 64 80 120