Gramáticas regulares
Gramáticas y lenguajes formales
Integrantes
Isabela Henao Garcı́a
Samuel Parra Murillo
Brandon Londoño Cano
Docente: Alexander Bejarano Gonzalez
Universidad Tecnológica de Pereira
Facultad de Ingenierı́as
Programa de Ingenierı́a de Sistemas y Computación
Pereira, 2025
Entrega del parcial II,3 Conceptos, formulación, ejemplos de la
exposición sobre gramáticas re. (Abril 7)
April 7, 2025
1 conceptos
Las gramáticas de tipo 3, también conocidas como gramáticas regulares
o gramáticas lineales a la derecha, son un subconjunto de las gramáticas
formales que generan los lenguajes regulares.
Estas gramáticas se caracterizan porque en sus reglas de producción, el
lado derecho de cada regla debe comenzar con un sı́mbolo terminal, que puede
ir seguido opcionalmente de un sı́mbolo no terminal. Su forma general es:
A → aB
A→a
donde:
• A, B son sı́mbolos no terminales (A, B ∈ VN ).
• a es un sı́mbolo terminal (a ∈ VT ).
Los lenguajes regulares son los más simples dentro de la Jerarquı́a de
Chomsky y se pueden describir mediante gramáticas regulares o recono-
cerse mediante autómatas finitos. Estos lenguajes pueden expresarse con
expresiones regulares.
En términos de gramáticas, existen dos tipos de lenguajes regulares:
• Lineales por la derecha: Las reglas de producción generan palabras
añadiendo sı́mbolos a la derecha de la cadena.
• Lineales por la izquierda: Las reglas generan palabras agregando sı́mbolos
a la izquierda de la cadena.
Un autómata finito es un modelo matemático de una máquina que acepta
cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto
finito de estados y un conjunto de transiciones entre esos estados, que dependen
de los sı́mbolos de la cadena de entrada. El autómata finito acepta una cadena
x si la secuencia de transiciones correspondientes a los sı́mbolos de x conduce
desde el estado inicial a un estado final. Además, permite determinar si las
cadenas pertenecen a un lenguaje regular.
1
2 Formulación
• Gramáticas Lineales a Derecha: el no terminal aparece después del
sı́mbolo terminal.
• Gramáticas Lineales a Izquierda: el no terminal aparece antes del
sı́mbolo terminal.
Estas gramáticas están estrechamente relacionadas con los autómatas fini-
tos, que pueden reconocer los lenguajes que generan.
Gramáticas Lineales a Derecha Una gramática es lineal a derecha si todas
sus producciones tienen la forma:
A → aB o A→a
donde:
• A, B son sı́mbolos no terminales, es decir, A, B ∈ N .
• a es un sı́mbolo terminal, es decir, a ∈ T .
• A puede ser el sı́mbolo inicial S.
Ejemplo Definimos la gramática G que genera cadenas que comienzan con
”a” y terminan con ”b”:
G = ({S, A}, {a, b}, P, S)
2
Con las reglas de producción:
S → aA
A→b
Derivación:
S ⇒ aA ⇒ ab
Caracterı́sticas:
• El sı́mbolo no terminal aparece después del terminal en cada pro-
ducción.
• Es ampliamente utilizada, ya que se relaciona directamente con los autómatas
finitos deterministas (AFD).
Gramáticas Lineales a Izquierda Una gramática es lineal a izquierda si
todas sus producciones tienen la forma:
A → Ba o A→a
donde:
• A, B son sı́mbolos no terminales, es decir, A, B ∈ N .
• a es un sı́mbolo terminal, es decir, a ∈ T .
• A puede ser el sı́mbolo inicial S.
Ejemplo Definimos una gramática G que genera cadenas que terminan en
”a” después de un ”b”:
G = ({S, A}, {a, b}, P, S)
Con las reglas de producción:
S → Aa
A→b
Derivación:
S ⇒ Aa ⇒ ba
Caracterı́sticas:
• El sı́mbolo no terminal aparece antes del terminal en cada producción.
3
• Se usa menos que la gramática lineal a derecha.
Producción S → ε En ambos tipos de gramáticas, se puede incluir la regla:
S→ε
para permitir que el lenguaje generado contenga la cadena vacı́a.
Tipo de Gramática Forma de las reglas Caracterı́stica clave
Lineal a derecha A → aB o A → a El no terminal aparece después del terminal
Lineal a izquierda A → Ba o A → a El no terminal aparece antes del terminal
¿Se permite S → ε? Sı́ Para incluir la cadena vacı́a en el lenguaje
3 Ejemplos
4
5
6
