Consider a new type of deterministic machine, having one read-only input tape and two stacks.The tape is read-only, it cannot be written, but the head can move left, right, or do nothing. Each stack operates, independently of the other, as in a deterministic pushdown automaton:

M= (K,,1,2,z1,z2,,s)

where K is a finite set of states, is a finite input alphabet, 1and 2 are two finite stack alphabets (1for the first stack, 2for the second stack),z1 1 and z2 2 are the initial symbols for the two stacks, s K is the initial state. h is a special halting state not in K,just like in a Turing machine.

(a) Give an appropriate definition for the transition function , for a configuration of this machine, for the yields in one step operator, and for the language accepted by this machine.

(b) These machines can accept the same languages as a class of automata you already know:deterministic pushdown automata, pushdown automata, or Turing machines? Prove your answer formally.