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:
- ∅ es una expresión regular
- ε es una expresión regular
- a ∈ Σun es una expresión regular para cadaa ∈ Σ
- si y son expresiones regulares, entonces
BUNsi
- A ⋅ B es una expresión regular (concatenación)
- A ∣ B 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,S∈N)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ε
- B→a
- B→aC
- B→ε
Gramáticas lineales izquierdas
Izquierda lineal gramáticas son los mismos, pero la regla # 2 es .B→Ca
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.