Existen muchos métodos para demostrar que un idioma no es regular , pero ¿qué debo hacer para demostrar que un idioma es regular?
Por ejemplo, si me dicen que es regular, ¿cómo puedo probar que la siguiente es regular?
¿Puedo dibujar un autómata finito no determinista para probar esto?
Respuestas:
Sí, si se te ocurre alguno de los siguientes:
para algún idiomaL , entonces L es regular. Hay modelos más equivalentes , pero los anteriores son los más comunes.
También hay propiedades útiles fuera del mundo "computacional".L también es regular si
puede construirlo realizando ciertas operaciones en idiomas regulares, y esas operaciones están cerradas para idiomas regulares , como
y más , o
En el ejemplo dado, tenemos un lenguaje (regular) como base y queremos decir algo sobre un lenguaje L ' derivado de él. Siguiendo el primer enfoque, construir un modelo adecuado para L ' , podemos asumir el modelo equivalente para L que deseamos; seguirá siendo abstracto, por supuesto, ya que L es desconocido. En el segundo enfoque, podemos usar L directamente y aplicarle propiedades de cierre para llegar a una descripción de L ' .L L′ L′ L L L L′
fuente
Métodos elementales
Métodos lógicos (a menudo utilizados en la verificación formal)
Métodos avanzados
Lemas sofisticados de bombeo. Véase, por ejemplo,
[1] J. Jaffe, Un lema de bombeo necesario y suficiente para los idiomas regulares, Sigact News - SIGACT 10 (1978) 48-49.
[2] A. Ehrenfeucht, R. Parikh y G. Rozenberg, Pumping lemmas for regular sets, SIAM J. Comput. 10 (1981), 536-541.
[3] S. Varricchio, una condición de bombeo para series regulares, SIAM J. Comput. 26 (1997) 764-771.
Bueno cuasi órdenes. Ver
[4] W. Bucher, A. Ehrenfeucht, D. Haussler, Sobre los reguladores totales generados por las relaciones de derivación, Theor. Comput Sci. 40 (1985) 131-148.
[5] M. Kunz, Soluciones regulares de desigualdades del lenguaje y cuasi órdenes .
Soporte de series racionales.N
Métodos algebraicos basados en transducciones (ver también Operaciones que preservan lenguajes regulares ).
fuente
La respuesta de Ran G. da una lista bastante extensa de los modelos equivalentes que se pueden usar para especificar idiomas regulares (y la lista continúa, autómatas bidireccionales, lógica MSO, pero eso está cubierto por el enlace bajo 'modelos más equivalentes '). Y como subraya Raphael, necesitamos un argumento para convencer al público de que la representación elegida es correcta.
Reconsiderando la pregunta, agrega 'Por ejemplo '. Eso significa que tenemos que dar una construcción válida que, dado cualquiera de los modelos anteriores que asumimos que especifique el lenguaje L , convierta ese modelo en uno para L ' . Por lo general, este será el mismo tipo de modelo, pero no necesariamente: podemos comenzar, por ejemplo, con una FSA determinista para L y terminar con una no determinante para L ' .… L L′ L L′
Esto incluye la posibilidad de usar operaciones de cierre: en la operación dada explícitamente en el ejemplo tenemos .L′=(Σ∗∖L)⋅Σ∗
fuente
<some property>
fuente
fuente
Un lenguaje es regular si puede escribir un escáner que decida sobre cadenas arbitrarias si pertenecen o no al idioma utilizando no más de una cantidad fija de memoria, es decir, el reconocimiento se puede hacer en el espacio O (1) .
fuente
La transformación de expresiones regulares es una forma de probar el cierre bajo ciertas operaciones. Los dos ejemplos más simples son cierre bajo inversión y cierre bajo homomorfismo .
fuente
Otra forma es construir el lenguaje usando operaciones bajo las cuales sabe que están cerradas. Esta es una extensión para exhibir una expresión regular, ya que tiene muchas más operaciones disponibles (invertir la cadena, complemento, intersección, cortar una pieza, solo mantener una parte, homomorfismos y homomorfismos inversos, ...)
fuente