How powerful are DFA with recursive calls?

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.

1. How to show any language accepted by a deterministic finite automaton with recursive calls is context-free?
2. Are all the languages accepted by deterministic finite automata with recursive calls deterministic context-free?
• What did you try? Where did you get stuck? Have you tried constructing a PDA for such a language? Did you get a deterministic one? – Shaull Oct 28 '17 at 18:13
• I'd try to convert the DFAs into a CFG as usual. Then, try replacing the terminals $1,\ldots,n$ so to achieve the "recursive calls". – chi Oct 28 '17 at 18:21