Les automates unidirectionnels alternatifs avec un guichet unique peuvent-ils reconnaître certaines langues unaires non régulières?

11

Les automates pushdown alternatifs unidirectionnels (1APDA) peuvent reconnaître n'importe quelle langue en (Alternation par Chandra, Kozen et Stockmeyer, 1981) . En remplaçant un stockage pushdown d'un 1APDA par un compteur, nous pouvons obtenir un automate alternatif unidirectionnel avec un compteur (1ACA). Ma question concerne 1ACA sur les langues unaires.TjeME(2O(n))

1ACA peut-il reconnaître certaines langues unaires non régulières ?

Notez que les automates de refoulement non déterministes unidirectionnels ne peuvent reconnaître que les langues régulières unaires.

Abuzer Yakaryilmaz
la source

Réponses:

6

Oui. Considérons le langage et construisons un automate à un compteur alternatif unidirectionnel reconnaissant de la manière suivante. Tout d'abord, l'automate commence à augmenter la valeur du compteur et devine quand s'arrêter, c'est-à-dire qu'il devine une valeur . Ensuite, elle se branche universellement: la première branche vérifie que la longueur de l'entrée est précisément de , et la deuxième branche avance de cellules vers l'entrée et vérifie que le reste est en , en passant à l'état de contrôle initial. Ajoutez maintenant un cas de base: laissez l'appareil accepter si la bande d'entrée est exactement de la longueurL={unenn=2s,s0}Lm2mmL1, en faisant une supposition non déterministe de l'état initial. Cela termine la construction.

De façon similaire, on peut obtenir des produits de la forme , avec fixes et arbitraires.n=k1s1krsrk1,,krs1,,sr

dd1
la source
1
Merci pour la réponse. J'ai obtenu la même réponse de Pavol Duris (via une communication privée) qui apparaîtra dans un article bientôt. J'avais l'intention de publier la réponse une fois que le document paraîtra en ligne. (Il peut y avoir des résultats encore plus forts.) Quoi qu'il en soit, votre réponse est certainement une réponse acceptée !
Abuzer Yakaryilmaz