so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}.

can i not just have one state (initial and final state) that loops a,b to itself?


  • 5
    $\begingroup$ Sure you can. What makes you think that it would be a problem? I suggest you write down formally the components of such a DFA, and see that they all fit the definitions. $\endgroup$
    – Shaull
    Mar 22 '16 at 5:51
  • $\begingroup$ @Shaull I thought that wouldn't be allowed because you can't create a RegEx for the language because of the infinite number of strings. And the wiki for DFAs states that a DFA "accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string." $\endgroup$ Mar 22 '16 at 5:57
  • 1
    $\begingroup$ Regular expressions can define infinite languages, for example $a^*$. Every word in the language is finite, but the language itself could be infinite. $\endgroup$ Mar 22 '16 at 6:34

A DFA is defined as a tuple $\langle \Sigma,Q,\delta,q_0,F \rangle$, with $\Sigma$ a finite alphabet, $Q$ a set of states, $\delta$ a transition function, $q_0$ an initial state, and $F\subseteq Q$ a set of accepting states.

Take $Q=F=\{q_0\}$ with $\delta(q_0,\sigma)=q_0$ for every $\sigma$. This DFA accepts every string, since it's run is always of the form $q_0,q_0,q_0,...,q_0$, and $q_0\in F$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.