Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal?
I'm studying for a test, and I found a question that asks if an infinite DFA could represent a regular language, and I want to use a regular DFA and add all the infinite states not connected to the original. Can I do that?
Asked By : Algosub
Answered By : Yuval Filmus
As babou mentions, infinite deterministic automata are rather powerful. In fact, they can compute all languages. Consider the "universal deterministic automaton" which is a $|\Sigma|$-ary infinite tree, with one state per each string in $\Sigma^*$. By choosing the set of accepting states to be $L \subseteq \Sigma^*$, we obtain an automaton which accepts $L$.
Regarding connectedness, while a DFA need not be connected, every disconnected DFA is equivalent to a smaller one which is connected; the minimal DFA is always connected.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23127
0 comments:
Post a Comment
Let us know your responses and feedback