15
$\begingroup$

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.

$\endgroup$
28
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – jmite Feb 4 at 18:24
  • 1
    $\begingroup$ Is language membership defined for infinite strings, and regular languages? $\endgroup$ – kutschkem Feb 5 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$ – Mr Redstoner Feb 6 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$ – Giacomo Alzetta Feb 6 at 14:22
  • $\begingroup$ The definition of a regular language is precisely those strings accepted by a DFA. An infinite string cannot be accepted by a DFA, so therefore it cannot be a member of a regular language. $\endgroup$ – chepner Feb 6 at 16:03
13
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.