Ineligenia.A

Universidad Americana de Acapulco
Excelencia para el Desarrollo
Facultad de Ingeniería
en Computación

Apuntes de Lenguajes
Formales y Autómatas

M. en C. José Mario Martínez Castro

Lenguajes Formales y Autómatas

Contenido del Curso
1. Introducción
2. Gramáticas regulares y autómatas de estado finito
3. Gramáticas de contexto libre y autómatas tipo push-down
4. Gramáticas decontexto sensitivo y autómatas tipo push-down doble
5. Gramáticas de estructura de frase y máquina de Turing
6. Autómatas lineales con frontera
7. Indecibilidad

Bibliografía
Hopcroft and Ullman
“Formal languages and their relation to automata”
Addson Wesley, E.E.U.U., 1969
Hopcroft and Ullman
“Introduction to automata theory, languages and computation”
Addson Wesley, E.E.U.U., 1979Índice General de Contenido
1. Introducción
1.1 Conceptos básicos y notación ............................................................ 1
1.2 Definición de operaciones con lenguajes ............................................. 6
1.3 Jerarquía de Chomsky........................................................................ 8
1.4 Gramáticas y Lenguajes..................................................................... 11
2. Gramáticas Regulares y Autómatas de Estado Finito
2.1 Expresiones Regulares ....................................................................... 15
2.2 Autómatas ....................................................................................... 17
2.2.1 Autómatas Finitos.................................................................... 17
2.2.2Autómatas Finitos No Determinísticos........................................ 21
2.2.3 Autómatas Finitos Determinísticos ............................................. 31
3. Derivaciones
3.1 Concepto ........................................................................................ 38
3.2 Tipos de Derivaciones....................................................................... 39
3.3Ambigüedad .................................................................................... 42

Unidad I

Introducción

1.1 Conceptos básicos y notación
1.2 Definición de operaciones con
lenguajes
1.3 Jerarquía de Chomsky
1.4 Gramáticas y lenguajes

Unidad 1. Introducción

1.1 Conceptos básicos y notación

Lenguajes Formales

Un lenguaje formal puede ser descrito por trescaracterísticas:
• Sintaxis
• Semántica
• Pragmática

Sintaxis y Gramática

La sintaxis es la especificación de la estructura de un lenguaje y la descripción de ésta.
La gramática contiene las reglas para generar o reconocer estructuras correctas.

Comparación entre los tipos sintácticos
de lenguajes naturales y de programación
Lenguaje Natural
Vocabulario
Símbolos alfabéticos
Marcas ysignos
Palabras
Clases de palabras
Sujetos
Verbos
Adjetivos
Adverbios
Etc.
Clases sintácticas de suboraciones
Predicado
Sujeto
Etc.
Tipos de Oraciones
Imperativas
Interrogativas
Exclamativas
Declarativas
Párrafos

Lenguaje de Programación
Vocabulario
Símbolos básicos
Símbolos elementales
Alfabéticos
Numéricos
Marcas y signos
Símbolos compuestos
Identificadores
Clasesde palabras
Dígitos
Letras
Enteros
Variables
Etc.
Clases sintácticas de subdeclaraciones
Expresiones
Aritméticas
Lógicas
Condicionales
Tipos de declaraciones
Declaraciones
Asignaciones
Secuenciales
Procedimientos
Bloques de Instrucción

1

Unidad 1. Introducción

Notación de la sintaxis en los lenguajes de Programación
Los manuales de programación definen la sintaxis endefiniciones estrictas, dentro de estas
definiciones podemos encontrar:
•
•
•

Notación Infija:
Notación Prefija:
Notación Postfija:

2+3
(+,2,3)
(2,3,+)

Para conformar una notación formal de las sintaxis para cualquier lenguaje fueron creados
los Diagramas de Sintaxis y la Notación BNF.

Forma Normal BNF (Backus Naur Form)
BNF es el acrónimo de Backus Naur Form. Corresponde a...