Los autómatas pushdown alternos unidireccionales (1APDA) pueden reconocer cualquier idioma en (Alternancia de Chandra, Kozen y Stockmeyer, 1981) . Al reemplazar un almacenamiento pushdown de un 1APDA con un contador, podemos obtener un autómata alternativo unidireccional con un contador (1ACA). Mi pregunta es sobre 1ACA en idiomas unarios.
¿Pueden los 1ACA reconocer algunos idiomas unarios no regulares ?
Tenga en cuenta que los autómatas pushdown no deterministas unidireccionales solo pueden reconocer lenguajes regulares unarios.
automata-theory
counter-automata
unary-languages
Abuzer Yakaryilmaz
fuente
fuente