2
$\begingroup$

I'm struggling with the definitions of the push-down automata. In 2-DPDA and 3-DPDA, what do the numbers 2 and 3 stand for: for the number of stacks or of read-only tapes (and hence RO heads) ?

Finally, is there a language accepted by k-DPDA but not with (k-1)-DPDA for any k ?

It seems that the last question is unsolved (a conjecture by Ibarra-Harrison) as of 1968:

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Please don't cross post (stackoverflow.com/questions/72664072/…) $\endgroup$
    – user19121278
    Jun 20, 2022 at 9:12
  • $\begingroup$ I had to cross: I wanted to migrate it as suggested by a comment there but I do not know how. $\endgroup$
    – user18624013
    Jun 20, 2022 at 15:54
  • $\begingroup$ Did you understand my answer? $\endgroup$
    – user19121278
    Jun 20, 2022 at 15:56
  • $\begingroup$ Yes, I've understood what is says but not how is that equivalence for $K\geq 2$ proved. It is stated as a conjecture in my source, is that correct ? $\endgroup$
    – user18624013
    Jun 20, 2022 at 16:01
  • $\begingroup$ If you post on the wrong site, please delete the copy on the old site and update your question based on the comments you've received, before posting on a new site. If you prefer to have it migrated, flag it for moderator attention ("in need of moderator intervention"), explain, and wait for them to act. You should never need to cross-post. Thank you! $\endgroup$
    – D.W. ♦
    Jun 20, 2022 at 19:19

2 Answers 2

Reset to default
0
$\begingroup$

$K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3. $That means for example $2{-}DPDA$ is capable of do the same work as $3{-}DPDA$ do, $2{-}DPDA$ is capable of do the same work as $4{-}DPDA$ do etc$.......... ... ... .. .. ..... .. .$

And $K{-}DPDA$ is equivalent to Turing Machine for any $K \geq2$$.$ $\{a^nb^nc^n\}$ is recognized by $2{-}DPDA$ but not by $1{-}DPDA$ or by $DPDA$ with $1{-}stack.$

Theorem1:- $\{a^nb^nc^n\}$ is recognized by $2{-}DPDA$.

Proof:- Suppose I have an two stacks $S_1$ with stack bottom $Z_0$ and $S_2$ with stack bottom $Z_1.$ Suppose consider the string $aabbcc$ is for $\{a^nb^nc^n\}.$

Step1. When $a$ will come push onto the stack $S_1$.

Step2. When $b$ will come two things happen.

  • push $b$ onto the stack $S_2.$
  • pop one $a$ from $S_1$ against one $b$.

Step3. When $c$ will come, pop one $b$ from $S_2$ against one $c.$

Step4. If you see finally two stacks $S_1$ with stack bottom $Z_0$ and $S_2$ with stack bottom $Z_1$ then strings are accepted otherwise rejected.

Theorem2:- $\{a^nb^nc^nd^n\}$ is recognized by $2{-}DPDA$.

Proof:- Suppose I have an two stacks $S_1$ with stack bottom $Z_0$ and $S_2$ with stack bottom $Z_1.$ Suppose consider the string $aabbccdd$ is for $\{a^nb^nc^nd^n\}.$

Step1. When $a$ will come push onto the stack $S_1$.

Step2. When $b$ will come two things happen.

  • push $b$ onto the stack $S_2.$
  • pop $a$ from $S_1$.

Step3. When $c$ will come two things happen.

  • push $c$ onto the stack $S_1.$
  • pop one $b$ from $S_2$ against one $c$.

Step4. When $d$ will come, pop one $c$ from $S_1$ against one $d.$

Step5. If you see finally two stacks $S_1$ with stack bottom $Z_0$ and $S_2$ with stack bottom $Z_1$ then strings are accepted otherwise rejected.

So we proved that $K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3.$

Note1:- You can easily check $\{a^nb^nc^nd^n\}$ by $3{-}stack$ that is your homework.

N. B.- $K{-}DPDA$ means $K{-}stack$ or $K{-}counter$ with $DPDA.$

Improve this answer
$\endgroup$
16
  • $\begingroup$ Please see my edit. Where is the result of equivalence proved in ? $\endgroup$
    – user18624013
    Jun 20, 2022 at 15:57
  • $\begingroup$ For real-time (k+1)-DPDA is better than k-DPDA but k-DPDA have caliber to accept that language that (k+1)-DPDA could do for k>=2. $\endgroup$
    – user19121278
    Jun 20, 2022 at 16:01
  • $\begingroup$ Right! But where can I find the hint for a proof of this nice result ? $\endgroup$
    – user18624013
    Jun 20, 2022 at 16:03
  • $\begingroup$ Could you accept a^nb^nc^n by 2 stack? It's known for you? $\endgroup$
    – user19121278
    Jun 20, 2022 at 16:05
  • $\begingroup$ I can believe but I've never seen a proof. $\endgroup$
    – user18624013
    Jun 20, 2022 at 16:05
0
$\begingroup$

Your image comes from M.Li and P.M.B. Vitányi: Kolmogorov Complexity and its Applications, Chapter 4 in Handbook of Theoretical Computer Science, vol. A, J. van Leeuwen Editor.

Both conjectures mentioned are of the form "(k+1)-head X automata are better than k-head X automata", so we can assume that k refers here to the numbers of heads on the (one-way) input tape of an X automaton. In the case of PDA that means there is only one pushdown stack available, but there are several heads that can read various portions of the input tape.

Note that even a finite state automaton can accept the non-context-free language $\{a^n b^n c^n \mid n\ge 1 \}$ if it has three heads that can move along the input tape. Each head moves to one of the letter segments, and synchronously they verify that the number of letters match.

The Harrison-Ibarra paper, Multi-Tape and Multi-Head Pushdown Automata. Inf. Control. 13(5): 433-470 (1968), is Open Archive, and can be accessed via the DOI: 10.1016/S0019-9958(68)90901-7

Here is the conjecture (page 462), with H for `heads', which explicitly proposed languages in the difference between two successive levels of an head-hierarchy:

Let $|\Sigma|\ge2$, and $c$ a symbol not in $\Sigma$. For each $n\ge > 2$, define the following sets: $L_2 = \{ xcx \mid x \Sigma*\}$ $L_{n+1} = \{xcycx \mid y \in L_n , x \in \Sigma^*\}$ (For example, $L_3 = \{ xcycycx \mid x, y \in \Sigma^*\}$ ). Then for each $n\ge 2$, $L_n$ is $n$-HDPDA definable but not $(n - 1)$-HPDA definable.

The conjecture is proven by Marek Chrobak, Ming Li: k+1 Heads Are Better than k for PDAs. J. Comput. Syst. Sci. 37(2): 144-155 (1988) DOI:10.1016/0022-0000(88)90004-9

Here a quote from that paper (which matches your image):

The following language was basically defined by Rosenberg [R] in order to show that $k + 1$ heads are better than $k$ heads for finite automata
$L_b = \{ w_1 \#\dots \# w_b \\\$ w_b \# \dots \#w_1 \mid w_i\in \{0,1\}^* \}$
[...] Amazingly, this language can also be used to serve our purpose although the proof technique is new.

The proof technique uses Kolmogorov complexity.

Improve this answer
$\endgroup$
10
  • $\begingroup$ You said Multihead dfa which can recognize $\{a^nb^nc^n\}.$ But multihead dfa is equivalent to classical dfa which shows contradiction. $\endgroup$
    – user19121278
    Jun 23, 2022 at 14:17
  • $\begingroup$ @user19121278 You can read this in the scan provided with the question: "(k+1)-head finite automata are better than k-head finite automata". $\endgroup$
    – Hendrik Jan
    Jun 23, 2022 at 14:51
  • $\begingroup$ That's true, but multihead dfa is equivalent to classical dfa. But here you are saying opposite. Where I have misunderstood, please guide me. $\endgroup$
    – user19121278
    Jun 23, 2022 at 15:37
  • $\begingroup$ "On the other hand, the condition $|u|=|2v|$ is indeed impossible to check for a classical, single tape, finite state automaton." But $|u|=|2v|$ is possible to implement with single tape classical DFA as like half of language $|u|=|v|?$ Am I correct? – For example $\{w1w2||w1|=|w2|\}$ is also regular and could be implemented by DFA. So my question how we implement this by dfa if they are not checked with single tape? This question have been torturing me from long time. Please help. I am waiting for your reply. $\endgroup$
    – user19121278
    Jun 23, 2022 at 18:54
  • 1
    $\begingroup$ Single head is not equivalent to multihead for finite state automata. See the example: with three heads you can do $\{ a^n b^n c^n \}$ by moving the heads along the three segments. That shows $|u|=|v|$ is not really possible to check when $u$ and $v$ are given on the input tape. Note $\{w_1w_2\mid |w_1|=|w_2| \}$ is a degenerate case: one does not check the segents separately. Compare with $\{w_1\# w_2\mid |w_1|=|w_2| \}$. For the "half"-language note that only $w_1$ is on the input tape, the existence of a matching $w_2$ is checked on the states of the automaton, not on the tape-symbols. $\endgroup$
    – Hendrik Jan
    Jun 23, 2022 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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