in Theory of Computation
327 views
0 votes
0 votes
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows say a*(b). Will the automaton not ‘hang’ if a string $a^n$ where $n \to$ ∞ is fed to it?
Isn’t ‘never accepting but progressing’ the same as hanging?
in Theory of Computation
327 views

1 Answer

0 votes
0 votes
If FA accepts the language (L) such that $a^n$ where $n \to$∞  

So even if the language is infinite but it is Countable and the string has to be finite sequence $w$ contain which can be accepted DFA or NFA

Another reason could be FA has limited tape so even if the string $w$ is infinite and it reached to Non final state that’s enough to reject string

Related questions