Diferencia entre la expresión regular y la gramática libre del contexto
Share
los diferencia principal entre la expresión regular y la gramática libre de contexto es que la las expresiones regulares ayudan a describir todas las cadenas de un lenguaje regular, mientras que la gramática sin contexto ayuda a definir todas las cadenas posibles de un lenguaje sin contexto.
La gramática denota reglas sintácticas para la conversación en lenguajes naturales. La ciencia de la computación utiliza la teoría de los lenguajes formales en gran medida. En el año 1956, Noam Chomsky dio un modelo matemático de gramática para escribir lenguajes de computadora. Cuando es posible derivar un conjunto de todas las cadenas de una gramática, se dice que el lenguaje se genera a partir de esa gramática. Dos tipos de gramática son la gramática regular y la gramática sin contexto. Cualquier lenguaje que pueda describirse con una expresión regular es un lenguaje regular. La gramática libre de contexto es una generalización de la expresión regular. Es posible usar expresiones regulares para escribir lenguajes regulares y gramática sin contexto para escribir gramática sin contexto.
Áreas clave cubiertas
1. ¿Qué es la expresión regular?
- Definición, ejemplos
2. ¿Qué es la gramática libre de contexto?
- Definición, ejemplos
3. Relación entre la expresión regular y la gramática libre del contexto
- Esquema de asociación
4. Diferencia entre la expresión regular y la gramática libre del contexto
- Comparación de diferencias clave
Términos clave
Expresión regular, gramática libre del contexto
¿Qué es la expresión regular?
La gramática regular genera lenguajes regulares. Esta gramática tiene un solo no terminal en el lado izquierdo y un lado derecho que consiste en un solo terminal o un solo terminal seguido de un solo no terminal. Puede tener una regla de producción de la siguiente manera.
X -> a o X -> a Y
Donde X, Y ϵ N (no terminal) y una ϵ T (terminal)
Las expresiones regulares ayudan a escribir gramática regular para describir lenguajes regulares.
Una expresión regular representa un determinado conjunto de cadenas de forma algebraica. Algunas reglas importantes a seguir al escribir una expresión regular son las siguientes.
- Los símbolos terminales, el símbolo nulo y el símbolo vacío son expresiones regulares.
- La unión de dos expresiones regulares es una expresión regular..
- La concatenación de dos expresiones regulares es una expresión regular.
- Iteración o cierre es una expresión regular..
La expresión regular para el conjunto 0,1,2 es la siguiente.
R = 0 + 1 + 2
El conjunto abb, a, b, bba se puede representar mediante la siguiente expresión regular.
R = abb + a + b + bba
Considere el conjunto, ϵ, 0, 00, 000, ...
La ϵ es la cadena vacía. La expresión regular es R = 0 *. Esto representa el cierre del símbolo incluyendo el símbolo vacío..
En el conjunto 1, 11, 111, 1111, ...
La expresión regular es R = 1 +. Esto + denota el cierre de un símbolo excluyendo el símbolo vacío.
¿Qué es la gramática libre de contexto?
En la teoría del lenguaje formal, Context Free Language (CFL) es un lenguaje generado por Context Free Grammar. Cuatro parámetros definen la gramática libre de contexto (G).
G = V, ∑, S, P
V: Conjunto de símbolos variables o no terminales.
∑: Conjunto de símbolos terminales
S: símbolo de inicio
P: Regla de producción
Context Free Grammar tiene el siguiente formato para la regla de producción.
A -> a donde a = V, ∑ * y A ϵ V
Un ejemplo de la gramática libre de contexto es el siguiente. Cada producción consta de un símbolo no terminal y una expresión regular.
Para generar un lenguaje que genere un número igual de a y b está en el formato de unnortesegundonorte. La gramática libre de contexto es la siguiente.
G = (S, A), (a, b), (S -> aAb, A -> aAb | ϵ)
Teniendo en cuenta el símbolo de inicio,
S -> a A b
Aplicando A -> aAb
→ a a a b b
Aplicando A -> aAb de nuevo,
→ a a a a b b b
Aplicando A -> ϵ (Este símbolo denota una cadena vacía)
→ a a a b b b
→ a 3 segundo 3
Cuando se considera la salida, el número de a es igual al número de b. Tiene la anorte segundonorte formar.
Relación entre la expresión regular y la gramática libre del contexto
- La gramática libre de contexto es una generalización de expresiones regulares..
Diferencia entre la expresión regular y la gramática libre del contexto
Definición
Una expresión regular es un concepto en la teoría del lenguaje formal que es una secuencia de caracteres que definen un patrón de búsqueda. La gramática libre del contexto es un tipo de gramática formal en la teoría del lenguaje formal, que es un conjunto de reglas de producción que describen todas las cadenas posibles en un lenguaje formal dado.
Uso
Las expresiones regulares ayudan a representar ciertos conjuntos de cuerdas de una manera algebraica. Ayuda a representar los idiomas regulares. La gramática sin contexto ayuda a definir todas las cadenas posibles de un lenguaje sin contexto.
Conclusión
Una expresión regular es un método para la coincidencia de patrones. Es un método flexible de proporcionar un medio flexible y conciso para unir cadenas de texto. Define todas las cadenas en el lenguaje regular. Por otro lado, la gramática sin contexto permite definir todas las cadenas que pertenecen a un lenguaje sin contexto. La diferencia entre la expresión regular y la gramática sin contexto es que las expresiones regulares ayudan a describir todas las cadenas de un lenguaje regular, mientras que la gramática sin contexto ayuda a definir todas las cadenas posibles de un lenguaje sin contexto.
Referencia:
1. "Expresiones regulares". Www.tutorialspoint.com, Tutorials Point, 8 de enero de 2018, disponible aquí.
2. "Introducción a la gramática sin contexto". Www.tutorialspoint.com, Tutorials Point, 8 de enero de 2018, disponible aquí.
Imagen de cortesía:
1. “Toolbaricon RegEx” Por M0tty - Trabajo propio (CC BY-SA 4.0) a través de Commons Wikimedia
