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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ what is "one-counter"? $\endgroup$
    – Ran G.
    Commented Mar 19, 2013 at 16:24
  • 1
    $\begingroup$ A PDA with only one kind of symbols (aside from the bottom symbol) on its stack. $\endgroup$
    – frafl
    Commented Mar 19, 2013 at 16:27
  • 1
    $\begingroup$ what do you mean by $x_{\lfloor|c|/2\rfloor}=a$ ? $\endgroup$
    – e_noether
    Commented Mar 20, 2013 at 4:20
  • 1
    $\begingroup$ @emmy: How would a (nondeterministic) 1CM decide $\overline{L}$? $\endgroup$
    – Shaull
    Commented Mar 20, 2013 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
    Commented Mar 20, 2013 at 13:07

1 Answer 1

Reset to default
-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

Improve this answer
$\endgroup$
4
  • 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
    Commented Mar 20, 2013 at 13:18
  • 1
    $\begingroup$ yeah :) just wanted to prove it can be done by 1-counter automata $\endgroup$
    – e_noether
    Commented Mar 20, 2013 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
    Commented Mar 20, 2013 at 13:26
  • 3
    $\begingroup$ Unfortunately, there is no proof here. $\endgroup$
    – Raphael
    Commented Mar 20, 2013 at 13:40

Your Answer

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

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