Question

A k-head pushdown automaton (k-PDA) is a deterministic pushdown automaton with k read-only, two-way input heads and a read/write stack. Define the class ${\mathbf{PDA}}_{\mathbf{K}}\mathbf{=}\mathbf{\{}\overline{)\mathbf{A}}$A is recognised by a $\mathbf{k}\mathbf{-}\mathbf{PDA}\mathbf{\}}$. Show that $\mathbf{p}\mathbf{=}{\mathbf{U}}_{\mathbf{k}}{\mathbf{PDA}}_{\mathbf{k}}$. (Hint: Recall that P equals alternating log space.)

Short answer

Given,$\mathbf{p}\mathbf{=}{\mathbf{U}}_{\mathbf{k}}{\mathbf{PDA}}_{\mathbf{k}}$ can be proved or achieved by using

$\mathbf{ASPACE}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}\mathbf{=}\mathbf{TIME}\mathbf{\left(}{\mathbf{2}}^{\mathbf{o}\mathbf{\left(}\mathbf{s}\left(n\right)\mathbf{\right)}}\mathbf{\right)}$, which shows that P is alternating log-space.

Step-by-step solution

Definition of a deterministic pushed down automaton

In automata theory, a deterministic pushed down automaton is a variation of the pushdown automation.

If a deterministic pushed down automation consists k read-only, a reader writes stack and two ways input heads then, it can be defined as a k-head-pushed-down automation $\mathbf{(}\mathbf{k}\mathbf{-}\mathbf{PDA}\mathbf{)}$.

${\mathbf{PDA}}_{\mathbf{K}}\mathbf{=}\mathbf{\{}\overline{)\mathbf{A}}$A is recognised by a $\mathbf{k}\mathbf{-}\mathbf{PDA}\mathbf{\}}$.

Constructing a machine M, with deterministic time 2o(s(n))

• The machine M with deterministic time ${\mathbf{2}}^{\mathbf{o}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}}$is used to simulate an alternating space $\mathbf{O}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}$machine S. The simulator M is given an input q and a graph is constructed by the simulator for the computation of S on q.
• The nodes are configured for S on q which use maximum Is(n) space, where l is the constant factor approximation for S.
• Edges are drawn from a configuration to those other configurations which can be generated in a single move of S.
• M Iteratively scans the graph and marks the configurations which are accepting, after the construction of the graph.
• Machine S continuously marks and scans nodes until no additional nodes are left.

Calculating configuration size

$\mathbf{P}\mathbf{=}{\mathbf{U}}_{\mathbf{k}}{\mathbf{PDA}}_{\mathbf{ka}}$

Given that localid="1657785375009" $\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\ge }\mathbf{logn}$and the configuration’s number of S on q is localid="1657785379079" ${\mathbf{2}}^{\mathbf{o}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}}$. Hence the configuration’s time and size are given by localid="1657785383153" ${\mathbf{2}}^{\mathbf{o}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}}$. Which is the same time taken to scan the graph once.

Here, the number of scans is equal to the maximum number of nodes in the graph. Therefore, the total time used is

From the above discussion it is known thatlocalid="1657785387244" $\mathbf{ASPACE}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}\mathbf{=}\mathbf{TIME}\mathbf{\left(}{\mathbf{2}}^{\mathbf{o}\mathbf{\left(}\mathbf{s}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{\right)}}\mathbf{\right)}$
and P is alternating log-space.

Hence, for localid="1657785390223" ${\mathbf{PDA}}_{\mathbf{K}}\mathbf{=}\mathbf{\{}\overline{)\mathbf{A}}$A is recognised by a localid="1657785392725" $\mathbf{k}\mathbf{-}\mathbf{PDA}\mathbf{\}}$, it can be said that .