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?
  • 2
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Oct 28 '17 at 18:13
  • $\begingroup$ 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". $\endgroup$
    – chi
    Oct 28 '17 at 18:21

Recursion is implemented on a computer using a stack, and your case is no different. You can use a stack to emulate the "call-and-return" semantics of your DFA with recursive calls, and the results will be a DPDA.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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