HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Can a deterministic finite automaton ever go into an infinite loop?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canfiniteinfiniteintoloopdeterministiceverautomaton

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#120307, answer score: 28

Revisions (0)

No revisions yet.