Automatas

Facultad: Ingeniería en Sistema de la Información
Estudiante: Manuel Estuardo Escobar López
Carne: 0906-10- 14748

Trabajo:
Gramáticas Regulares y expresiones regulares
Definición yejemplos

Ing. Luis Mendoza
Curso: Lenguajes Formales y automatas
Sección: “Única”

Coatepeque, agosto 2012
-------------------------------------------------
GRAMATICAS REGULARES -EXPRESIONES REGULARES

Gramáticas

Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del Lenguaje.

Una gramática formal es una cuadrupla G = (N, T, P, S)donde
- N es un conjunto finito de símbolos no terminales
- T es un conjunto finito de símbolos terminales N ∩ T = ∅
- P es un conjunto finito de producciones
Cadaproducción de P tiene la forma
α → β, α = ϕAρ y β = ϕωρ
ϕ, ω, ρ ∈ (N ∪ T)
y A es S ó A ∈ N
- S es el símbolo distinguido o axioma S ∉ (N ∪ T)

Restringiendolos formatos de producciones permitidas en una gramática, se pueden especificar

Cuatro tipos de gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.

Gramáticas regulares(Tipo 3)

Generan los lenguajes regulares (aquellos reconocidos por un autómata finito). Son las gramáticas

Más restrictivas. El lado derecho de una producción debe contener un símboloterminal y, como máximo, un símbolo no terminal. Estas gramáticas pueden ser:

- Lineales a derecha, si todas las producciones son de la forma
A ∈N ∪ {S}
A → aB ó A → a B ∈ N
a ∈ T
(en el lado derecho de las producciones el símbolo no terminal aparece a la derechadel símbolo terminal)

- Lineales a izquierda, si todas las producciones son de la forma
A ∈ N ∪ {S}
A → Ba ó A → a B ∈ N...