Existe-t-il un langage à compteur unique strictement non déterministe dont le complément est à compteur unique?

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

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

Est-ce le cas que ? $A = \text{Deterministic one-counter}$

Je sais que pour les langues sans contexte, l'analogue n'est pas le cas. Par exemple, laissez . Alors et sont sans contexte mais n'est pas déterministe. Par conséquent, définit un sous-ensemble (strict) des langages sans contexte. $P =\{ ww^r\}$ $P$ $\bar{P}$ $P$ $A$

La question est: pouvons-nous construire un exemple à guichet unique similaire pour lequel il en est de même?

formal-languages automata closure-properties pushdown-automata e_noether
la source

qu'est-ce que le "guichet unique"?

Ran G.19

Un PDA avec un seul type de symboles (à part le symbole du bas) sur sa pile.

frafl

que voulez-vous dire par ?

x_{⌊ | c | / 2 ⌋} = a

$x_{\lfloor|c|/2\rfloor}=a$

e_noether

@emmy: Comment un 1CM (non déterministe) déciderait-il

\bar{L}

$\overline{L}$ ?

Shaull

@emmy: Oups, faute de frappe: je voulais dire bien sûr

x_{⌊ x / 2 ⌋}

$x_{\lfloor x/2\rfloor}$ c'est-à-dire le symbole au

⌊ x / 2 ⌋

$\lfloor x/2\rfloor$ -th position.

frafl

Réponses:

-1

En réponse au commentaire de Shaull ci-dessus: entrez la description de l'image ici

Le premier est une image de 1 compteur acceptant $a^ib^j$ st $j<i$

Le secong est une image d'acceptation de 1 compteur $a^ib^j$ st $j>i,\ j<2i$

Le troisième est une image de 1 compteur acceptant $a^ib^j$ st $j>2i$

Ici, un / - / plus signifie voir un, quelle que soit la valeur du compteur, incrémenter le compteur. b /> 1? / sub signifie en voyant b, si la valeur du compteur est supérieure à 1, décrémenter le compteur.

nop => aucune opération

$\lambda$ => chaîne vide

e_noether
la source

Une réponse assez longue qui est essentiellement juste "Parce que c'est l'union de trois langues, chacune reconnaissant un intervalle de

i

$i$ s par rapport à

j

$j$ ".

frafl

ouais :) je voulais juste prouver que cela peut être fait par des automates à 1 compteur

e_noether

Il est correct d'élaborer un peu, surtout si c'est un bon exercice pour vous, mais veuillez ajouter un bref résumé. De plus, vous ne devez pas utiliser de réponse pour répondre à un commentaire, mais dans ce cas, cette réponse peut devenir une réponse réelle à votre question, donc je pense que c'est OK aussi.

frafl

Malheureusement, il n'y a aucune preuve ici.

Raphael