Gramáticas formales: La representación de los lenguajes regulares se fundamentan en la noción de gramática formal. Una gramática es un conjunto de reglas para formar correctamente las frases de un lenguaje; así tenemos la gramática del español. La formalización que presentaremos de la noción de gramática es debida a Chomsky, y está basada en las llamadas reglas gramaticales.
Gramáticas regulares: Las expresiones regulares como las gramáticas son distintas formas de especificar a los lenguajes regulares . Una gramática regular (lineal a derecha) es una cuádruplo G = (V, T, P, S) donde :
V es un conjunto finito de símbolos llamados variables o símbolos no terminales,
T es un conjunto finito de símbolos, llamados terminales, satisfaciendo T ∩ V = ∅,
P ⊆ V × (T ∗ V ∪ T ) es un conjunto finito de elementos, llamados producciones, de manera tal que si (p, q) ∈ P se denotará mediante la expresión p → q; p recibe el nombre de cabeza y q el de cuerpo de la producción, y
S ∈ V es el símbolo inicial.
Está definición puede darse en términos de gramáticas lineales a izquierda. Afortunadamente, dicha elección no tiene relevancia alguna puesto que son equivalentes.
Ejemplo:
Expresión regular: (0 + 1)∗ 01(0 + 1)∗.
Dicha expresión describe el conjunto de las cadenas de ceros y unos que continen la subcadena 01.
La gramática: que describe el lenguaje asociado a (0 + 1)∗ 01(0 + 1)∗ viene dada por las producciones siguientes:
S → 0S
S → 1S
S → 01S '
S → 0S '
S → 1S y
S → ε.
Más compactamente,
S → 0S|1S|01S '
S → 0S|1S|ε.
Gramáticas regulares: Las expresiones regulares como las gramáticas son distintas formas de especificar a los lenguajes regulares . Una gramática regular (lineal a derecha) es una cuádruplo G = (V, T, P, S) donde :
V es un conjunto finito de símbolos llamados variables o símbolos no terminales,
T es un conjunto finito de símbolos, llamados terminales, satisfaciendo T ∩ V = ∅,
P ⊆ V × (T ∗ V ∪ T ) es un conjunto finito de elementos, llamados producciones, de manera tal que si (p, q) ∈ P se denotará mediante la expresión p → q; p recibe el nombre de cabeza y q el de cuerpo de la producción, y
S ∈ V es el símbolo inicial.
Está definición puede darse en términos de gramáticas lineales a izquierda. Afortunadamente, dicha elección no tiene relevancia alguna puesto que son equivalentes.
Ejemplo:
Expresión regular: (0 + 1)∗ 01(0 + 1)∗.
Dicha expresión describe el conjunto de las cadenas de ceros y unos que continen la subcadena 01.
La gramática: que describe el lenguaje asociado a (0 + 1)∗ 01(0 + 1)∗ viene dada por las producciones siguientes:
S → 0S
S → 1S
S → 01S '
S → 0S '
S → 1S y
S → ε.
Más compactamente,
S → 0S|1S|01S '
S → 0S|1S|ε.
