¿Existe un análogo de "regular" para cadenas infinitas?

Considere la secuencia . Parece "regular" de una manera que, por ejemplo, no lo es. $s_1 = (1, 0, 1, 0,\dots)$ $s_2 = (1, 2, 3, 4,\dots)$

Sin embargo, no estoy seguro de cómo formalizar esta intuición. Una cosa que me llama la atención es que es un lenguaje regular, y es, en cierto sentido, el límite de las cadenas en este idioma. $L =\{(0 1)^n\}$ $s_1$

¿Existe una terminología para considerar estas cadenas infinitas? ¿Tenemos algo análogo al lema de bombeo, mediante el cual podemos afirmar que cualquier cadena "regular infinita" tiene la forma con , , finita? $x y^ {\infty}z$ $x$ $y$ $z$

formal-languages regular-languages Xodarap
fuente

Quizás periódico o eventualmente periódico .

Yuval Filmus el

Bombeo : su afirmación sobre cadenas infinitas no es análoga al Lema de bombeo , que dice que palabras suficientemente largas en un lenguaje regular contienen una subcadena que puede repetirse para producir otra palabra. ¡No dice que todas las palabras tengan esa forma!

PJTraill

Terminología : se habla de que una cadena es regular, mientras que el término regular se aplica normalmente a los idiomas.

PJTraill

Respuestas:

Probablemente el término más específico para describir su primera cadena, $010101\dots$ es periódica . Una cuerda $x_1x_2\dots$ (finito o infinito) es periódico si hay alguna $t$ tal que, para todos $i$ , $x_i=x_{i+t}$ . En el caso de este ejemplo, podemos tomar $t=2$ . Una noción ligeramente más débil es que una cadena es eventualmente periódica si hay $n$ y $t$ tal que $x_i=x_{i+t}$ para todos $i\geq n$ .

Sin embargo, en términos más generales, existe un análogo directo de los idiomas regulares, que es el $\omega$ -lenguajes regulares . Estos son reconocidos por generalizaciones naturales de autómatas finitos. El conjunto de estados todavía es finito, pero el criterio de aceptación debe modificarse para tratar con palabras infinitas; en particular, no podemos decir simplemente "Aceptar si el autómata termina en un estado de aceptación" porque el autómata nunca termina de procesar su entrada infinita.

La clase más simple de autómatas para palabras infinitas son los autómatas Büchi . Se definen exactamente como los autómatas finitos a los que está acostumbrado, y aceptan su entrada si se visita al menos un estado de aceptación infinitamente durante la ejecución del autómata. Una diferencia de los autómatas finitos ordinarios es que resulta que los autómatas Büchi no deterministas son más poderosos que los deterministas, y el $\omega$ -los lenguajes regulares son los aceptados por los autómatas no deterministas de Büchi. Otros criterios de aceptación razonables conducen a otros modelos de autómatas que aceptan la misma clase de idiomas.

Tenga en cuenta que no tiene mucho sentido escribir $xy^\omega z$ , ya que no puedes tener nada después de una secuencia infinita de $y$ s. Al menos, no puede si las posiciones en su cadena están indexadas por los números naturales. Si están indexados por ordinales más grandes, esto puede tener sentido.

En realidad no puedo recordar si hay un análogo del lema de bombeo para $\omega$ -lenguajes regulares. Esto es un poco vergonzoso, aunque ha pasado casi una década desde que enseñé una clase de posgrado sobre estas cosas.

David Richerby
fuente

Agradable. Quizás agregue explícitamente que

ω

$\omega$ -las lenguas regulares son uniones finitas de lenguas

A B^{ω}

$AB^\omega$ , dónde

A, B

$A,B$ regular. No sé sobre bombeo, pero a veces es útil observar que cada

ω

$\omega$ El lenguaje regular debe contener una cadena eventualmente periódica.

Hendrik Jan

Siempre he odiado la presentación estándar del lema de bombeo por ser tan malditamente obtuso. Cuando se llega al final, todo lo que realmente dice es que, dado que hay un conjunto finito de estados, cualquier cadena con más símbolos que estados debe visitar algún estado dos veces durante una ejecución del autómata. Los símbolos que participan en este ciclo son los que puede "bombear". Bajo esta luz, está claro que hay un análogo cuando hacemos la transición a cadenas infinitas pero conservamos estados finitos; entonces la pregunta no es "¿hay un lema de bombeo?" pero "¿cuánto más complicado es el lema de bombeo?".

Daniel Wagner

@DanielWagner: Wow, sí ... la presentación estándar es bastante obtusa y la tuya lo deja muy claro. ¡Gracias por esa explicación!

user541686

@DanielWagner: el lema de bombeo ciertamente es confuso, pero la ventaja de la presentación estándar es que no se refiere a la mecánica de autómatas, expresiones regulares o cualquier otra forma particular de definir lenguajes regulares. ¡Solo habla de cuerdas!

Max

@Max ¡Una ventaja dudosa de hecho!

Daniel Wagner

Este es un resultado básico en la efectividad de tipo dos, que creo que responde a su pregunta desde un punto de vista computable. A continuación, nuestros idiomas consisten solo en cadenas infinitas. Denotamos el conjunto de cuerdas infinitas $\Sigma^\omega$ .

Teorema: si un autómata realizable termina en cada cadena infinita, entonces el lenguaje del autómata es igual a $S\Sigma^\omega$ dónde $S$ es un conjunto finito de cadenas finitas.

La prueba es por el lema de Konig.

La conclusión es que un lenguaje sobre cadenas infinitas es "simple" en algún sentido (que es un hecho interesante ) o indecidible. Cualquier noción no trivial del lenguaje sobre cadenas infinitas es indecidible.

Presumiblemente, puede estudiar idiomas menos simples si permite que la membresía sea semidecidible en lugar de decidible. Esto todavía puede considerarse "informática" y no solo matemática infinita (tiene que ver con problemas de búsqueda en lugar de problemas de decisión; la semidecidabilidad es, en cierto sentido, suficiente para hacer una búsqueda).

ogogmad
fuente