Sé que los lenguajes que se pueden definir usando expresiones regulares y aquellos reconocibles por DFA / NFA (autómatas finitos) son equivalentes. Tampoco existe DFA para el idioma . Pero aún así puede escribirse usando expresiones regulares (para el caso, cualquier lenguaje no regular puede ser) como . Pero sabemos que cada lenguaje que tiene una expresión regular tiene un DFA que lo reconoce (contradicción con mi declaración anterior). Sé que esto es algo trivial, pero ¿la definición de expresión regular incluye la condición de que debería ser finita?
10
Respuestas:
Si se permitiera que las expresiones regulares fueran infinitas, cualquier lenguaje habría sido regular.
Teniendo en cuenta el lenguaje , siempre podemos definir la expresión regular R = w 1 + w 2 + ⋯ , que define exactamente L . (Ejemplo: la expresión regular R 1 = ϵ + 0 + 1 + 00 + 01 + 10 + 11 + ⋯ define L 1 = { 0 , 1L = { w1, w2, ... } R = w1+ w2+ ⋯ L
R1= ϵ + 0 + 1 + 00 + 01 + 10 + 11 + ⋯ .)L1= { 0 , 1 }∗
Sabemos que algunos idiomas no son regulares, por lo que esto muestra que las expresiones regulares infinitas describen una clase de idiomas más grande que las expresiones regulares finitas.
fuente
Sí, debe ser finito. Imagine que tiene ese conjunto infinito de posibles coincidencias, y su entrada es
011
. ¿Alguna vez podrás rechazarlo? ¿Alguna vez te quedarás sin partidos para comprobar?¿Hay algún lenguaje que, según esa definición, no sea regular ? ¿Qué pasa con el conjunto de todos los pares de programas y entradas de modo que el programa dado se detenga en la entrada dada?
Ahora, si tuviera un programa que enumerara las cadenas en un idioma en orden lexicográfico:
Actualizar
Para aclarar un poco en función de los comentarios en los comentarios, la razón por la que no todos los idiomas de este formulario son regulares es por definición. Si, por ejemplo, busca la prueba del teorema de Kleene, depende del hecho de que una expresión regular debe ser finita para demostrar que genera una máquina de estados finitos.
¿Por qué definimos el lenguaje "regular" de esa manera? Debido a que cada idioma formal es un subconjunto de las cadenas en un alfabeto, y cada conjunto de cadenas se puede expresar como una unión de singletons, por lo que si llamamos a cualquier conjunto de cadenas un lenguaje "regular", el lenguaje regular sería simplemente un sinónimo de idioma . Esa no es una definición muy útil, especialmente porque en realidad no podemos implementarla en hardware o software. No podemos almacenar una lista infinita arbitraria en ningún lado ni construir una máquina de estado infinito.
Sin embargo, como insinué, si tiene una manera de enumerar todas las cadenas en un idioma en orden, puede construir un decisor a partir de eso (acepte cuando vea esa cadena exacta, rechace cuando encuentre una cadena que viene después de la que usted está buscando) y viceversa (para cada cadena en orden, ejecútela a través del decisor y envíela si y solo si es aceptada). Entonces, si consideramos que cada lenguaje enumerable es regular , cada lenguaje decidible sería "regular" y necesitaríamos un nuevo término para los idiomas reconocidos por las máquinas de estados finitos y sus codificaciones equivalentes como expresiones finitas.
fuente
Supongamos que se permite que las expresiones regulares sean infinitas.
Por lo tanto, el lenguaje definido por {ϵ} ∪ {01} ∪ {0011} ... será regular. Para cada idioma regular existe un NFA. Una forma de obtener este NFA sería tener NFA individuales para cada uno de {ϵ}, {01}, {0011} ... y combinarlos usando transiciones ϵ. Como hay infinitas expresiones regulares distintas, necesitaremos infinitos sub-NFA para combinar. Sin embargo, la NFA solo puede tener un número finito de estados (definición de NFA).
Por lo tanto, no existe un NFA que pueda definir un lenguaje definido por la unión de infinitas expresiones regulares, lo que implica que el lenguaje no es regular.
Por lo tanto, no existe una expresión regular que pueda definir el mismo lenguaje que el lenguaje definido por la unión de infinitas expresiones regulares.
Por lo tanto, las expresiones regulares solo pueden tener expresiones finitas.
fuente