Automatas

Páginas: 274 (68346 palabras) Publicado: 6 de noviembre de 2013
Teor´ de Aut´matas y Lenguajes Formales
ıa
o
Alvaro E. Campos
Pontificia Universidad Cat´lica de Chile
o
Escuela de Ingenier´
ıa
Departamento de Ciencia de la Computaci´n
o
Marzo 1995

Contents
0 PROLOGO
0.1 ¿Qu´ es un Lenguaje? . . . .
e
0.2 Sintaxis versus Sem´ntica . .
a
0.3 Los Problemas a Estudiar . .
0.4 Aplicaci´n a Otros Problemas
o
0.5 Clases de Lenguajes . . . . .0.6 Otros Problemas a Estudiar .
0.7 Problemas No Decidibles . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

´
´
1 MATEMATICAS BASICAS
1.1 Conjuntos . . . . . . . . . . . . . .
1.1.1 Operaciones con Conjuntos
1.1.2 Conjuntos Infinitos . . . . .
1.2 Inducci´n Matem´tica . . . . . . .
o
a
1.2.1 Otras Bases . . . . . . . . .
1.2.2 Inducci´n Completa . . . .
o1.2.3 Definiciones Inductivas . . .
1.3 Grafos y Arboles . . . . . . . . . .
1.3.1 Grafos Dirigidos . . . . . .
´
1.3.2 Arboles . . . . . . . . . . .
1.4 Relaciones Binarias . . . . . . . . .
1.4.1 Propiedades . . . . . . . . .
1.4.2 Relaciones de Equivalencia
1.4.3 Clausuras . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
..
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

5
5
5
6
6
7
8
8

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
..
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
..
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

9
9
10
11
12
13
14
15
17
17
18
19
20
21
22

2 LENGUAJES FORMALES
2.1 S´
ımbolos y Alfabetos . . . . . . . . . .
2.2 Palabras . . . . . . . . . . . . . . . . .
2.2.1 Longitud de una Palabra . . .
2.2.2 Concatenaci´n . . . . . . . . .
o
2.2.3 Subpalabras, Prefijos y Sufijos2.2.4 Reverso . . . . . . . . . . . . .
2.3 Lenguajes . . . . . . . . . . . . . . . .
2.3.1 Concatenaci´n de Lenguajes . .
o
2.3.2 Clausuras . . . . . . . . . . . .
2.3.3 Representaci´n de Lenguajes .
o
2.4 Aut´matas . . . . . . . . . . . . . . .
o

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

....
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Automata

    ...Tarea Numero 3 Autómata Fecha 23/Agosto/2010 Autómatas cuánticos A mí en particular me interesa desde un punto de vista netamente de la teoría de lenguajes. En esta entrada voy a presentar una propuesta de autómata: La teoría de automatas es una rama de las ciencias de la computación que estudia de manera abstracta y con problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente...

    Leer más
    731 Palabras 3 Páginas
  • Automatismos

    ...Ensayo Principios de los sistemas automáticos INSTITUTO TECNOLÓGICO DE LOS MOCHIS ING. ELECTRÓNICA Controladores Lógicos Programables Salcedo Flores Luis Felipe 07440620 2010 02/10/2010 Ensayo Principios de los sistemas automáticos INSTITUTO TECNOLÓGICO DE LOS MOCHIS ING. ELECTRÓNICA Controladores Lógicos Programables Salcedo Flores Luis Felipe 07440620 2010 02/10/2010 Principios de un sistema automático El...

    Leer más
    1552 Palabras 7 Páginas
  • automata

    ...profesor: Módulo: Autómatas finitos deterministas Actividad: Diseño de un autómata finito Fecha: 21 septiembre 2013 Bibliografía: -Apuntes de clase. -Información disponible en ftp://ftp.icesi.edu.co/abustamante/Material%20Inf%20Te%F3rica/Cap2.pdf Objetivo: Obtener el diseño de un autómata que lea cadenas compuestas por 0 y 1, pero solo aquellas en las que el antepenúltimo numero sea 1. Procedimiento: Determinar las condiciones...

    Leer más
    728 Palabras 3 Páginas
  • Automatas

    ...AUTÓMATAS PROBABILÍSTICOS O ESTOCÁSTICOS En su funcionamiento interviene el concepto de probabilidad, asociada a que se produzca una determinada transición. Son autómatas finitos en los que las transiciones entre estados a partir de símbolos de entrada pueden no producirse de forma segura (probabilidad = 1) sino que existe una determinada probabilidad asociada a que se produzca la transición. No se habla del estado en el que se encuentra el...

    Leer más
    902 Palabras 4 Páginas
  • Automatismo

    ...EMPLEO INTERRUMPIDO EMPLEO A 8 HORAS EMPLEO TEMPORAL EMPLEO INTERMITENTE Esquema de trabajo El circuito de potencia es una representación de elementos y líneas que alimenta las cargas Esquema de mando Es una representación de la lógica del automatismo, donde podemos ver el funcionamiento y la función de los distintos elementos. Pulsadores Aparatos de maniobra uso contacto o contactos, cambian de posición solamente cuando una fuerza externa sobre ellos. Rasante: el...

    Leer más
    1192 Palabras 5 Páginas
  • Automatas

    ...´ AUTOMATAS DE ESTADO FINITO Orlando Arboleda Molina ´ Escuela de Ingenier´a de Sistemas y Computacion de ı La Universidad del Valle 12 de octubre de 2008 Contenido ´ Automatas de estado finito ´ Concatenacion de conjuntos de cadenas Clausura de Kleene ´ Automatas de estado finito deterministas ´ Automatas de estado finito no deterministas ´ ´ Una de las aplicaciones mas importantes de las maquinas de estado finito es el...

    Leer más
    972 Palabras 4 Páginas
  • Autómatas

    ...DE LOS AUTÓMATAS FINITOS INTRODUCCIÓN Los autómatas finitos constituyen un modelo que nos permite representar un sistema, es útil para diferentes tipos de hardware y software, como: software para diseñar y probar el comportamiento de circuitos digitales, analizador léxico, software para explorar cuerpos de texto largos y software para verificar sistemas que tengan un número finito de estados diferentes. A continuación, en el presente ensayo se analizan...

    Leer más
    778 Palabras 4 Páginas
  • Automatismo

    ...AUTOMATISMO Movimiento pictórico que parte del hecho de que se puede crear dé y a partir de todo, la creatividad pura solo pertenece a la naturaleza y por tanto aprendemos a copiar a través de la observación atenta, la intuición y la atención suspicaz al inconsciente. Automatismo gráfico • Método de realización de pinturas y dibujos mediante el cual el artista suprime el control consciente sobre los movimientos de la mano con la intención de que aflore su...

    Leer más
    1265 Palabras 6 Páginas

OTRAS TAREAS POPULARES

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS