0
$\begingroup$

Does there exist a general approach in mainstream academia for representing a deterministic infinite automata? Unlike the finite kind, this one with infinite number of states.

Although there is infinite state. There is a finite number of types of states. E.g. state $inBrackets_k$ goes to state has an edge leading to $inBrackets_{k+1}$ when receiving input '('. $inBrackets$ can be considered the class/type of those infinity many states. (Thats a language of balanced brackets handle by deterministic infinite state machine example).

Further more. Could deterministic infinite automata be minimised. I.E. Minimise the number of types of states, using the same approach we use for the finite kind?

$\endgroup$
9
  • $\begingroup$ I get the feeling an deterministic infinite automata is equal to a PDA. So no minimise number of states algorithm should exist. $\endgroup$
    – clinux
    Commented Jun 15, 2022 at 4:44
  • $\begingroup$ Algorithm to minimise number of types of states I mean. (There is always an infinite number of states.) $\endgroup$
    – clinux
    Commented Jun 15, 2022 at 5:13
  • 2
    $\begingroup$ Infinite DFAs accept all languages, so it’s not an interesting model of computation. $\endgroup$ Commented Jun 15, 2022 at 5:32
  • $\begingroup$ Actually deterministic infinite automata is probably equal to a turing machine. $\endgroup$
    – clinux
    Commented Jun 15, 2022 at 5:32
  • $\begingroup$ What do you mean by minimization? All countably infinite sets have the same cardinality. $\endgroup$ Commented Jun 15, 2022 at 5:33

2 Answers 2

3
$\begingroup$

As Yuval Filmus explains, every language can be recognized by an infinite-state DFA. So, it is not a concept that is of much interest in computability and automata theory.

Of course you can represent an infinite-state DFA using the same mathematical formulation as a finite-state DFA. The standard definition of a DFA says that it is a tuple $(Q,\Sigma,\delta,q_0,F)$ where $Q$ is a finite set of states, etc. If you simply allow $Q$ to be infinite but keep everything else the same, you can use the same formulation to represent an infinite-state DFA. So no special approach is needed.

Minimization requires some care to define, as all countably infinite sets have the same cardinality.

I wonder if you're actually looking for the notion of a pushdown automaton.

$\endgroup$
7
  • 2
    $\begingroup$ You can still ask for the minimal DFA, whose states are the Myhill–Nerode equivalence classes. It is still minimal in the sense that it is a homomorphic image of any other DFA for the same language. $\endgroup$ Commented Jun 15, 2022 at 5:45
  • $\begingroup$ @YuvalFilmus, good point, thank you! $\endgroup$
    – D.W.
    Commented Jun 15, 2022 at 5:47
  • $\begingroup$ I was more wondering why a google search of infinite DFA returns nothing. When there is plenty of knowledge about the finite kind. The existance of PDA would be that reason. $\endgroup$
    – clinux
    Commented Jun 15, 2022 at 5:49
  • $\begingroup$ A general minimisation algorithm of PDA does not exist today. But who knows in future. $\endgroup$
    – clinux
    Commented Jun 15, 2022 at 5:51
  • 1
    $\begingroup$ @clinux, cs.stackexchange.com/q/37461/755 $\endgroup$
    – D.W.
    Commented Jun 15, 2022 at 5:55
0
$\begingroup$

Besides what has been said, I wonder: what kind of real physical device would such a thing (a deterministic infinite automata) modelize?

I mean, a Turing machine has an infinity of possible states but at least you can start running it with a bounded memory (limiting it to $n$ reachable states), then after some run time if you have exhausted the memory you can "buy more RAM" and rerun the machine with $n^2$ reachable states and so on.

That's why it is sometimes called an unbounded memory model of computation (not infinite).

Unless you assume more about the infinite states automata (like you have a function which bounds the number of accessible states after n steps), you would have to provide an infinite amount of memory right from the start... and that is not physically possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.