8
$\begingroup$

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $ A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example, let $P =\{ ww^r\}$. Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic. Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?

$\endgroup$
  • 2
    $\begingroup$ what is "one-counter"? $\endgroup$ – Ran G. Mar 19 '13 at 16:24
  • 1
    $\begingroup$ A PDA with only one kind of symbols (aside from the bottom symbol) on its stack. $\endgroup$ – frafl Mar 19 '13 at 16:27
  • 1
    $\begingroup$ what do you mean by $x_{\lfloor|c|/2\rfloor}=a$ ? $\endgroup$ – e_noether Mar 20 '13 at 4:20
  • 1
    $\begingroup$ @emmy: How would a (nondeterministic) 1CM decide $\overline{L}$? $\endgroup$ – Shaull Mar 20 '13 at 8:08
  • 1
    $\begingroup$ @emmy: Ooops, typo: I meant of course $x_{\lfloor x/2\rfloor}$ i.e. the symbol at the $\lfloor x/2\rfloor$-th position. $\endgroup$ – frafl Mar 20 '13 at 13:07
-1
$\begingroup$

In response to Shaull's comment above : enter image description here enter image description here

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j>i,\ j<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter. b/>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop => no operation

$\lambda $ => empty string

$\endgroup$
  • 1
    $\begingroup$ Quite a long answer which is essentially just "Because its the union of three languages, each recognizing one interval of $i$s relative to $j$". $\endgroup$ – frafl Mar 20 '13 at 13:18
  • 1
    $\begingroup$ yeah :) just wanted to prove it can be done by 1-counter automata $\endgroup$ – e_noether Mar 20 '13 at 13:20
  • 2
    $\begingroup$ It's OK to elaborate a bit especially if it's a nice exercise for you, but please add a short summary. Additionally you should not use an answer to reply to a comment, but in this case this reply may become an actual answer to your question, so I think it's OK, too. $\endgroup$ – frafl Mar 20 '13 at 13:26
  • 3
    $\begingroup$ Unfortunately, there is no proof here. $\endgroup$ – Raphael Mar 20 '13 at 13:40

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.