¿Cómo demostrar que un idioma es regular?

48

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 L es regular, ¿cómo puedo probar que la siguiente L es regular?

L:={wL:uv=w for uΣL and vΣ+}

¿Puedo dibujar un autómata finito no determinista para probar esto?

corium
fuente
1
hay un error tipográfico en la definición de su L , edite para corregir.
Ran G.
2
"Dibujar" no es una prueba; tienes que dar un NFA y demostrar que acepta el idioma.
Rafael
Creo que la definición del lenguaje todavía no tiene sentido ...
hugomg
2
de todos modos, el lenguaje específico es irrelevante si la pregunta es "¿puedo dibujar un NFA para demostrar que es regular"? @corium, ¿podemos editar la pregunta para reflejar la pregunta más general: "cómo demostrar que una específica Les regular"?
Ran G.

Respuestas:

48

Sí, si se te ocurre alguno de los siguientes:

para algún idioma L , 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

  • es finito
  • puede construirlo realizando ciertas operaciones en idiomas regulares, y esas operaciones están cerradas para idiomas regulares , como

    • intersección,
    • complemento,
    • homomorfismo
    • inversión,
    • cociente izquierdo o derecho,
    • transducción regular

    y más , o

  • usando el teorema de Myhill-Nerode si el número de clases de equivalencia para es finito.L

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 ' .LLLLLLL

Sonó.
fuente
44
También vale la pena señalar que demostrar que un idioma es finito es suficiente para demostrar que es regular. Eso puede ser útil, particularmente en pruebas no constructivas por casos.
Patrick87
2
Las expresiones regulares que se encuentran en los lenguajes de programación pueden hacer mucho más que los lenguajes normales. Tendría que restringirse a construcciones "clásicas".
David Lewis
44
@DavidLewis: En este sitio, puede suponer que por "expresión regular" se entiende la noción clásica.
Raphael
@DavidLewis Estoy de acuerdo, uno debe evitar "regexp" en el contexto de la teoría para evitar confusiones.
Raphael
Tenga en cuenta que para cualquiera de las primeras cuatro viñetas, necesitará una prueba que demuestre que su representación es correcta.
Raphael
10

Métodos elementales

  1. Autómatas finitos (posiblemente no deterministas, con transiciones vacías).
  2. Expresiones regulares.
  3. Ecuaciones lineales derechas (o izquierdas, pero no ambas), como donde K y L son regulares.X=KX+LKL
  4. Gramática regular (tipo 3).
  5. Operaciones que preservan lenguajes regulares (operaciones booleanas, producto, estrella, shuffle, morfismos, inversos de morfismos, inversión, etc.)
  6. Reconocido por un monoide finito.

Métodos lógicos (a menudo utilizados en la verificación formal)

  1. Lógica monádica de segundo orden (teorema de Büchi).
  2. Lógica temporal lineal (teorema de Kamp).
  3. El teorema del árbol de Rabin (lógica monádica de segundo orden con dos sucesores). Muy poderoso.

Métodos avanzados

  1. 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.

  2. 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 .

  3. Soporte de series racionales.N

  4. Métodos algebraicos basados ​​en transducciones (ver también Operaciones que preservan lenguajes regulares ).

J.-E. Alfiler
fuente
4

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 ' .LLLL

Esto incluye la posibilidad de usar operaciones de cierre: en la operación dada explícitamente en el ejemplo tenemos .L=(ΣL)Σ

LL

Hendrik Jan
fuente
1
L
@ Raphael Lo siento, hice mi punto. Las respuestas anteriores parecen explicar que podemos construir una descripción del lenguaje (como autómata, operaciones, etc.). Estoy de acuerdo. Sin embargo, la pregunta parece ser sobre las propiedades de cierre, vea el ejemplo dado. Ese punto me falta en las otras respuestas: para probar una propiedad de cierre, asumes que tienes una descripción y construyes una nueva.
Hendrik Ene
1
L
1
LLLLLLLLL
1
Oh ok En realidad, prefiero editar la pregunta, y quitar la parte "por ejemplo", con lo que la cuestión más general, y una referencia para futuras preguntas similares .. (:
Ran G.
4

sks<some property>kk

Rick Decker
fuente
4

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Q1×Q2×{1,2}xiyi
  • q0=q01,q02,1
  • F=F1×F2×{1}
  • δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0
  • Q=Q{q0}
  • q0
  • q0
  • δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

q0


R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • F={q,q,2:qQ}δ(q0,x)=q
  • δ(q0,ϵ)={q,q,1:qQ}q
  • δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • Q=Q×{0,,k}
  • q0=q0,0
  • F=F×{0,,k}
  • q,σ,iδ(q,σ),iδ(q,i,σ)
  • q,i+1δ(q,i,σ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
fuente
3

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) .

reinierpost
fuente
O (1) espacio, quieres decir? En cualquier caso, esto está cubierto por el hecho de que DFA es suficiente; Puede valer la pena señalar explícitamente esta equivalencia en términos de programación.
Raphael
Sí, es solo una perspectiva diferente.
reinierpost
3

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 .

rLLRL

  • ϵR=ϵσR=σR=
  • (r1+r2)R=(r1R+r2R)(r)R=(rR)(r1r2)R=r2Rr1R

(r1r2)R=r2Rr1R(01)R=10rRLR

h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
fuente
0

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, ...)

vonbrand
fuente
2
Eso ya se menciona en la respuesta de Ran.
Raphael