As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
12
A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.
-
$\begingroup$ To add to this, a Two-Way DFA can go into an infinite loop on finite input, but every two-way DFA is equivalent to a loop-free one-way DFA. $\endgroup$– jmiteFeb 4, 2020 at 18:24
-
1$\begingroup$ Is language membership defined for infinite strings, and regular languages? $\endgroup$ Feb 5, 2020 at 9:57
-
$\begingroup$ @kutschkem Wasn't given the definitions we used during the uni formal languages course. For that matter for us strings were defined as finite sequences to begin with. But under definitions that permit infinite strings it may be possible to also amend the definitions for the various models to make it work. $\endgroup$ Feb 6, 2020 at 12:55
-
$\begingroup$ @kutschkem Lookup Buchi automata. Typically when dealing with infinite strings the acceptance condition changes. Instead of "when you read the string you end up in an acceptance state" you say (for example) "when reading this infinite string you pass through an acceptance state an infinite number of times". There are a few alternatives that give rise to different automata which may or may not have different levels of power in recognizing languages of infinite strings. For example: typically non deterministic automata are not equivalent to deterministic ones. $\endgroup$ Feb 6, 2020 at 14:22
-
1$\begingroup$ @chepner A two-way automaton is defined specifically to not (necessarily) do that: instead of consuming the input one character at a time, the transition function dictates which way the read head moves on the input tape. So there's nothing stopping it from moving left->right->left->right... But these loops are detectable, so we can always make an equivalent one-way DFA. $\endgroup$– jmiteFeb 6, 2020 at 18:17
$\begingroup$
$\endgroup$
The DFA performs a single state transition on each read input symbol, reads each symbol of the input exactly once, and halts when the input string is exhausted. In order for an infinite loop of state transitions to happen, the input string has to be infinite. DFAs are usually defined for finite inputs only, as the automaton's output is defined by what state the automaton is in after the input string has been exhausted (something that will never happen for infinite strings).
However, the concept of the DFA has been generalized in a way it can be applied to infinite input strings as well: the omega automata (often written as ω-automata) will accept a string if the entire execution fulfills some acceptance condition. A typical example is the Büchi automaton, which functions otherwise as a normal DFA or NFA, but only accepts input strings that cause the automaton to be in an accepting state infinitely often.
