Los lenguajes omega-regulares son conjuntos de palabras infinitas que pueden ser reconocidas por autómatas finitos. Más precisamente, un conjunto de palabras infinitas es omega-regular si existe un autómata finito que, al leer una palabra del conjunto, visitará algunos estados del conjunto de estados de aceptación infinitamente. Un autómata finito que tiene este tipo de condición de aceptación se llama autómata Büchi.
Si pensamos en el alfabeto subyacente como un conjunto finito de posibles eventos del programa, podemos pensar en una palabra infinita como una secuencia de eventos y en un lenguaje omega-regular como el conjunto de secuencias de eventos para las cuales ciertos eventos ocurren infinitamente a menudo. De esta manera, los autómatas de Büchi pueden usarse para describir propiedades de programas que no terminan y pueden considerarse como una representación gráfica de tales propiedades.
En cuanto a los lenguajes regulares ordinarios, hay una clase de expresiones regulares que capturan exactamente los lenguajes omega-regulares. Estas son las llamadas expresiones omega-regulares. Se puede pensar en las expresiones omega-regulares como un lenguaje para describir propiedades de cálculos infinitos, y se puede demostrar que las expresiones omega-regulares pueden describir con precisión las propiedades que se pueden describir en una lógica temporal de tiempo lineal.
- ¿Cuál es la ecuación matemática correcta para el siguiente problema informático?
- ¿Puede un desarrollador web beneficiarse de la CS teórica? ¿Cómo puede ser eso?
- En matemáticas y ciencias de la computación, ¿cuál es / hay una diferencia entre las funciones calculables y computables?
- Informática teórica: ¿cómo empiezo a resolver el problema P = NP?
- ¿Cómo podemos escribir un código eficiente para determinar números primos hasta un valor dado, de modo que el límite de tiempo para cada caso de prueba no exceda un segundo en lenguaje C?
Un buen lugar para leer más es el capítulo de la encuesta de Wolfgang Thomas Automata on Infinite Objects.
