Is there a strictly non-deterministic one-counter language whose complement is one-counter?
In response to Shaull's comment above :



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

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j&gt;i,\ j&lt;2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j&gt;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