A family of deterministic finite automata of degree n over an alphabet , with N = , consists of a set M = {(Ki , {1, . . . , n}, i ,si , Fi) : 1 i n} of deterministic finite automata. We fix implicitly a subscript function over M, so that we can refer to the i-th automaton Mi = (Ki , {1, . . . , n}, i ,si , Fi) of M. Such a family performs the following processing:

Given an input w , the automaton M1 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, . . . , n}. It then gives control to the automaton Mi . The automaton Mi processes the not yet consumed input until it reaches a final state. When such a state is reached, Mi terminates and gives control back to M1, which resumes its operation from state p. M1 accepts the input iff it is in a final state when the end of the input is reached.

More generally, any automaton Mi can call some other automaton Mj , which happens whenever Mi performs a transition of form i(q, j) = p. When such a thing happens, Mi gives control to Mj . When the operation of Mj reaches a final state, Mi 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. Show that 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? Justify your answer.