Diferencia entre expresión regular y gramática en autómatas

12

Soy nuevo en los autómatas, y ayer me dieron una breve introducción a las expresiones regulares. He leído las diversas reglas para definir una expresión regular. Pero no puedo diferenciar entre las expresiones regulares y la gramática de un idioma (no me han enseñado la gramática de las expresiones regulares).

Entiendo que la gramática nos ayuda a generar las cadenas válidas en un idioma, pero esto es lo que establecen las reglas para definir expresiones regulares. Entonces, ¿dónde radica la diferencia? Le pregunté a mi profesor y él dijo que las expresiones regulares son las cadenas más básicas en un idioma y que la gramática es el conjunto de reglas para cualquier idioma, que son de orden superior a las expresiones regulares. ¿Alguien puede proporcionar información más detallada?

Charu Bansal
fuente

Respuestas:

22

Las expresiones regulares, las gramáticas regulares y los autómatas finitos son simplemente tres formalismos diferentes para la misma cosa. Hay algoritmos para convertir de cualquiera de ellos a cualquier otro.

La razón básica de que tengamos los tres es que fueron creados de forma independiente, con el primer conjunto de equivalencias (también hay varios otros formalismos) probados por Kleene (este resultado, o parte del mismo, se llama Teorema de Kleene).

Entonces, en ese contexto, dependiendo de la forma en que desee ejecutar los modelos, todos reconocen o generan cadenas de un lenguaje regular, y matemáticamente, en ese sentido, no hay diferencia.

Por supuesto, a veces un modelo es más fácil de usar que otro para una tarea particular, debido a los detalles del formalismo. Además, la forma en que funcionan en la cabeza de un humano es a menudo un poco diferente, los autómatas finitos "se sienten" como computadoras, las expresiones regulares "se sienten" como si estuvieras construyendo una cadena de subcadenas más pequeñas y las gramáticas regulares "se sienten" como una gramática más tradicional derivación o clasificación de una oración en un idioma (como era de esperar cuando se mira el historial).

Entonces, para comparar los dos, definámoslos:

Expresiones regulares

Por lo tanto, las expresiones regulares se definen recursivamente de la siguiente manera:

  1. es una expresión regular
  2. ε es una expresión regular
  3. a Σa es una expresión regular para cadaaΣ
  4. si y son expresiones regulares, entonces BAB
    • AB es una expresión regular (concatenación)
    • AB es una expresión regular (alternancia)
    • A es una expresión regular (estrella de Kleene)

Junto con algunas semánticas (es decir, cómo interpretamos los operadores para obtener una cadena), obtenemos una forma de generar cadenas a partir de un lenguaje regular.

Gramáticas regulares

Las gramáticas regulares consisten en cuatro tuplas donde es el conjunto de no terminales, es el conjunto de terminales, es el inicio no terminal y es el conjunto de producciones que nos dicen cómo cambiar el símbolo de inicio, paso a paso, en una cadena en . puede tener sus producciones extraídas de uno de dos tipos (aunque no de ambos):N Σ S P Σ P(N,Σ,P,SN)NΣSPΣP

Gramáticas lineales derechas

Para los no terminales , , terminal y la cadena vacía , todas las reglas tienen la forma:C a εBCaε

  1. Ba
  2. BaC
  3. Bε

Gramáticas lineales izquierdas

Izquierda lineal gramáticas son los mismos, pero la regla # 2 es .BCa

Cosas para reflexionar

Entonces, mirando estas definiciones y jugando con ellas, podemos ver que las expresiones regulares se parecen a reglas coincidentes, o formas de tratar las cadenas de a poco.

Las gramáticas parecen "etiquetar" secciones de la cadena y agrupar etiquetas bajo nuevas etiquetas para validar la cadena (es decir, si podemos pasar de a la cadena, o viceversa, estamos contentos).S

Sin embargo, estos realmente están haciendo lo mismo fundamental, y la forma en que veas la metáfora de su función depende de ti.

Luke Mathieson
fuente
Pondría más énfasis en el hecho de que las gramáticas generan cadenas en el lenguaje, mientras que las expresiones regulares (como dijiste) son más un patrón coincidente que coincide (o "prueba") con cada cadena en el lenguaje.
Ran G.
@RanG., Esa es de hecho la forma habitual de pensarlo, pero puedes dar la vuelta a ambos; el análisis de abajo hacia arriba prueba una cadena contra una gramática, y puede usar una expresión regular como una descripción compacta de un lenguaje (aunque esto es probablemente menos común).
Luke Mathieson el
@simpleBob es el conjunto de no terminales, es el no terminal inicial. ¿Cuál sería ? S RNSR
Luke Mathieson
@LukeMathieson Mi error, leí el párrafo y pensé que era un error tipográfico con debido al orden en que se definióAhora que he leído la definición formal en otra parte, parece que el error tipográfico era que debería ser (creo) (segunda línea en el primer párrafo de las gramáticas regulares)R R PNRRP
Daniel
@simpleBob, Ah sí, definitivamente es un error tipográfico. ¡Gracias!
Luke Mathieson