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?
thanks
$\begingroup$
$\endgroup$
-
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$ – billy jacoberson 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$ – Yuval Filmus Mar 22 '16 at 6:34
$\begingroup$
$\endgroup$
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$.
