A family of deterministic finite automata of degree $n$ over an alphabet $Σ$, with $\bigcap Σ = ∅$, consists of a set $\mathcal{A} =\{(K_i,Σ∪\{1,\dots,n\},δ_i,s_i,F_i) : 1 ≤ i ≤ n\}$ of deterministic finite automata. We fix implicitly a subscript function over $\mathcal{A}$, so that we can refer to the “$i$-th automaton $\mathcal{A}_i = (K_i, Σ ∪ \{1, \dots, n\}, δ_i, s_i, F_i)$ of $\mathcal{A}$.”
Such a family performs the following processing:
Given an input $w ∈ Σ^∗$, the automaton $\mathcal{A}_1$ starts processing the input as usual, following the transitions in $δ_1$, until it reaches a transition of the form $δ_1(q, i) = p$, with $i ∈ \{1, \dots, n\}$. It then gives control to the automaton $\mathcal{A}_i$. The automaton $\mathcal{A}_i$ processes the not yet consumed input until it reaches a final state. When such a state is reached, $\mathcal{A}_i$ terminates and gives control back to $\mathcal{A}_1$, which resumes its operation from state $p$. $\mathcal{A}_1$ accepts the input iff it is in a final state when the end of the input is reached.
More generally, any automaton $\mathcal{A}_i$ can “call” some other automaton $\mathcal{A}_j$, which happens whenever $\mathcal{A}_i$ performs a transition of the form $δ_i(q, j) = p$. When such a transition happens, $\mathcal{A}_i$ gives control to $\mathcal{A}_j$. When the operation of $\mathcal{A}_j$ reaches a final state, $\mathcal{A}_i$ takes the control back and resume its operation starting from state $p$.
Call the whole system a deterministic finite automaton with recursive calls. It is in fact a usual finite automaton, with the added functionality that some edges represent a call to a different automaton instead of the acceptance of one input symbol.
- How to show any language accepted by a deterministic finite automaton with recursive calls is context-free?
- Are all the languages accepted by deterministic finite automata with recursive calls deterministic context-free?
