Question & Answer: Define an "infinite automata" similarly to finite automata, but where the state set Q is no longer restricted to be finite. Characterize pre…..

An automation can be described as finite representation of a formal language that may be an infinite or a finite set. Automata are often classified by the class of formal languages they can recognize. Infinite automata are of interest not only in the verification of systems with infinite state spaces, but also as a natural (even somehow underdeveloped) framework for the study of formal languages. So infinite automata can be classified as an automation that accepts infinite words (ω-words) that may not have a finite number of states, or even a countable number of states. Such automata are called ω-automata. The analysis of infinite transition systems is of central interest in infinite-state and the system verification at the same time one of the most promising application domains of automata theory.

The infinite-state automata we study can be defined by using words to represents the states of the automaton. Let us fix a finite alphabet Σ as the input alphabet for the infinite-state automata. The set of states of an infinite-state automaton over Σ are words over a finite alphabet Π (which does not need to be related to Σ in any way). The initial and final sets of states of this automaton are defined using word-languages over Π accepted by finitely presented devices (e.g. finite-state automata over Π). Transitions between states are defined using rewriting rules that rewrite words to other words: for each a ∈ Σ, we have a rewrite rule that rewrites words over Π. A state u ∈ Π∗ leads to state u′ ∈ Π∗ on a ∈ Σ iff the rewrite rule for a can rewrite u to u′. There is a variety of choices for the power of rewriting, but in any case the rewriting rules are presented finitely (e.g. using finite transducers). The language accepted by an infinite state automaton is defined in the natural way: a word w ∈ Σ∗ is accepted if there is a path from some initial state to some final state tracing w in the automaton.

The standard definitions for finite/infinite are like a finite language is any set LL of strings, of finite cardinality, |L|<∞|L|<∞. An infinite language is any set LL of strings, of infinite (ℵ0ℵ0) cardinality |L|=∞|L|=∞.

A finite LL is always regular.

An infinite LL can be regular (sometimes called “finite-state”), decidable (sometimes called “recursive”), non-regular (non-finite-state), non-decidable, etc.

The class of languages accepted by deterministic infinite automata are number of widely different and equi-expressive formalisms precisely capture the same class of languages:

• The infinite automaton characterization for the class 2ETIME, the class of languages accepted by Turing machines in time exp(exp(O(n)))3, using a qualitative constraint on rewriting, which is a restricted form of multi-stack pushdown rewriting.

Any language in 2ETIME is accepted by an infinite-state bounded-phase pushdown transducer automata, thereby completing the proof that such automata exactly characterize 2ETIME.

We briefly sketch a BPTA A that accepts a word w if and only if w is accepted by a 2 O(n) space Turing machine M. First A guesses a word w and a run t of M encoding them as a sequence of pairs of words (ui, vi) such that all the steps taken in t, and w along with the initial configuration, are all represented by at least one such pair. Then, it checks if the guessed sequence indeed encodes an accepting run of M on w.

In the first task we make use of a slight variation of a standard encoding of trees by words where each pair of consecutive configurations of M are written consecutively in the word. The second task is by Lemma 6. We observe that it suffices to have single initial and final states for A.

Unlike a deterministic ω-automation (infinite automation), which has a transition function δ, the non-deterministic version has a transition relation Δ. We must note that Δ can be regarded as a function: Q × Σ → P(Q) from Q × Σ to the power set P(Q). Thus, given a state qn and a symbol an, the next state qn+1 is not necessarily determined uniquely, rather there is a set of possible next states.

A run of A on the input α = (a1,a2,a3,…) is any infinite sequence ρ = (r0,r1,r2,…) of states that satisfies the following conditions:

r0 is an element of Q0.

r1 is an element of Δ(r0,a1).

r2 is an element of Δ(r1,a2).

…

rn is an element of Δ(rn-1,an).

A nondeterministic ω-automation (infinite automation) may have many different runs on any given input, or none at all. The input is accepted if at least one of the possible runs is accepting. Whether a run is accepting depends only on Acc, as for deterministic ω-automata. Every deterministic ω-automaton can be regarded as a nondeterministic ω- automation (infinite automation) by taking Δ to be the graph of δ. The definitions of runs and acceptance for deterministic ω-automata(infinite automata) are then special cases of the nondeterministic cases.