Automatas Finitos

Páginas: 132 (32804 palabras) Publicado: 24 de noviembre de 2012
´
UNIVERSIDAD POLITECNICA DE VALENCIA
´
´
DEPARTAMENTO DE SISTEMAS INFORMATICOS Y COMPUTACION

Aut´matas finitos: Irreducibilidad
o
e Inferencia

Tesis Doctoral presentada por Manuel V´zquez de Parga Andrade
a
Dirigida por Pedro Garc´ G´mez
ıa o
Valencia, Junio 2007

´
Indice
1. Introducci´n.
o

3

2. Lenguajes y Aut´matas finitos.
o
2.1. Alfabetos, palabras y lenguajes.. . . . . . . . . . .
2.2. Aut´matas finitos. . . . . . . . . . . . . . . . . . .
o
2.3. Aut´matas finitos deterministas. . . . . . . . . . .
o
2.4. Otros tipos de aut´matas finitos. . . . . . . . . . .
o
2.4.1. Aut´matas finitos con transiciones vac´
o
ıas. .
2.4.2. RFSA (Residual Finite State Automaton).
2.4.3. Aut´matas maximales asociados a lenguajes
o
2.5. Operaciones sobreaut´matas finitos. . . . . . . . .
o
2.5.1. Cocientes. . . . . . . . . . . . . . . . . . . .
2.5.2. Reverso. . . . . . . . . . . . . . . . . . . . .
2.5.3. Subaut´matas. . . . . . . . . . . . . . . . .
o
2.5.4. Homomorfismos. . . . . . . . . . . . . . . .
2.5.5. Uni´n. . . . . . . . . . . . . . . . . . . . . .
o
2.5.6. Determinizaci´n. . . . . . . . . . . . . . . .
o
2.5.7. Minimizaci´n. . . . .. . . . . . . . . . . . .
o
2.6. Aut´mata Universal. . . . . . . . . . . . . . . . . .
o

.....
.....
.....
.....
.....
.....
finitos.
.....
.....
.....
.....
.....
.....
.....
.....
.....

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

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

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

5
5
6
8
10
10
10
11
13
13
1414
15
15
16
16
16

3. Inferencia gramatical de lenguajes regulares.
3.1. Inferencia gramatical. . . . . . . . . . . . . . . .
3.2. Inferencia gramatical de lenguajes regulares. . . .
3.2.1. Conceptos b´sicos. . . . . . . . . . . . . .
a
3.2.2. El algoritmo Trakhtenbrot-Barzdin-Gold.
3.2.3. El algoritmo RPNI. . . . . . . . . . . . .
3.2.4. Inferencia no determinista. . . . . . . ..

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

19
19
21
21
22
23
25

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

4. Minimalizaci´n de Aut´matas Finitos.
o
o
4.1. Introducci´n. . . . . . . . . . . . . . . . . . . . . . .
o
4.2. Minimalidad. . . . . . . . . . . . . . . . . . . . . . .
4.2.1.Aut´matas finitos minimales. . . . . . . . . .
o
4.2.2. Minimalidad relativa. . . . . . . . . . . . . .
4.3. Irreducibilidad. . . . . . . . . . . . . . . . . . . . . .
4.3.1. Aut´matas finitos irreducibles. . . . . . . . .
o
4.3.2. Estados fusionables. . . . . . . . . . . . . . .
4.3.3. Estados fusionables y el aut´mata universal. .
o
4.3.4. Irreducibilidad relativa. . . . . . . . . . . ..
4.4. Concisi´n. . . . . . . . . . . . . . . . . . . . . . . . .
o
4.4.1. Aut´matas finitos concisos. . . . . . . . . . .
o
4.4.2. Estados superfluos. . . . . . . . . . . . . . . .
4.4.3. Aut´matas finitos concisos irreducibles. . . .
o
4.4.4. Concisi´n relativa. . . . . . . . . . . . . . . .
o
1

29
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

29
29
29
31
32
32
33
35
38
41
41
42
43
44

4.4.5. Irreducibilidad y concisi´n relativas. . . . . . . . . . . . .
o
5. Redes de aut´matas cocientes.
o
5.1.Red de cocientes de un aut´mata finito. .
o
5.2. Completitud y universalidad estructural. .
5.2.1. Aplicaciones a la inferencia de L3 .
5.3. Semired de cocientes asociada a un par de
5.3.1. Aplicaciones a la inferencia de L3 .

...........
...........
...........
aut´matas finitos.
o
...........

.
.
.
.
.

.
.
.
.
.

45
49
49
50
55
56
60

6. Inferencia mediante...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • AUTOMATAS FINITOS

    ... E M M A D E B O L EMPRESA MANUFACTURERA DE BOLSOS 1 FORMULACION DEL PROYECTO Observando la necesidad que se presenta en los internos de la penitenciarias carcelarias de Colombia, de ser rehabilitados para que puedan ser útiles a la sociedad y se abstengan de volver a cometer los mismo errores que lo condujeron a caer en una prisión; pero cuando se habla de una rehabilitación no solamente se refiere a enseñarles la parte teórica que en muchas ocasiones se...

    Leer más
    1433 Palabras 6 Páginas
  • Automatas Finitos

    ...Qué son? El autómata finito es un modelo de un sistema que trabaja con entradas y salidas discretas, este posee configuraciones conformadas por estados los cuales están asociados a un símbolo de entrada de un alfabeto finito sigma. Los autómatas finitos son una manera matemática para describir clases particulares de algoritmos, estos se puede utilizar para describir el proceso de reconocimiento de patrones en cadenas de...

    Leer más
    828 Palabras 4 Páginas
  • Automatas finitos

    ...INFORMATICA TEÓRICA Curso 2008-2009 Prácticas Tema 4 AUTÓMATAS FINITOS Práctica 4.1: Construcción de autómatas finitos. 1.- Construir autómatas finitos deterministas que reconozcan los siguientes lenguajes: L1= { am bn⏐ m > 0, n > 0 } L2 = { x ∈ {0,1}* ⏐ en x aparece el 1 dos o tres veces, la primera y la segunda de las cuales no son consecutivas } L3 = { x ∈ {a,b}* ⏐ Na(x) es par } L4 = { x ∈ {a,b}* ⏐...

    Leer más
    673 Palabras 3 Páginas
  • Automatas finitos

    ...AUTÓMATAS FINITOS DETERMINISTAS Un autómata finito determinista (abreviado AFD), denominémoslo M, es una máquina teórica que se utiliza para reconocer cadenas de un lenguaje regular, llamémoslo L. Se puede describir como una quíntupla, así: M= (S, Σ, δ, t, F), donde, S es un conjunto finito de estados. Σ es el alfabeto de la máquina (el conjunto de símbolos con los que se conforman las cadenas del lenguaje L)....

    Leer más
    1014 Palabras 5 Páginas
  • AUTOMATAS FINITOS

    ...EJERCICIOS SQL 1. Crear una consulta que permita mostrar el apellido y salario de los empleados que ganan más de 12 000 select last_name, salary from employees where salary>12000; 2. Crear una consulta que permita mostrar el apellido y el número de departamento del empleado No. 176 select employee_id, last_name, department_id from employees where employee_id=176; 3. Crear una consulta que permita mostrar el apellido y salario de los empleados que su salario no esta...

    Leer más
    1383 Palabras 6 Páginas
  • Automatas Finitos

    ...Juan Carlos Segundo Galindo Programación Avanzada, 10/04/2012 Ejemplo 7.1 Descripción: Lectura de veinte enteros de un vector denominado F. Código Fuente: static void Main(string[] args) { int[] F = new int[21]; for (int i = 1; i <= 20; i++) { Console.WriteLine(" *** Escribe un valor" + i); F[i] = int.Parse(Console.ReadLine()); Console.WriteLine("** Vector: " + F[i]);...

    Leer más
    700 Palabras 3 Páginas
  • Automata Finito

    ...AUTÓMATA FINITO Autómata del griego automatos (αὐτόματος) que significa espontáneo o con movimiento propio. Autómata: Máquina que imita la figura y los movimientos de un ser animado. Autómata programable: Equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales. No tiene sus propios movimientos, sino que estos...

    Leer más
    1318 Palabras 6 Páginas
  • Autómata finito

    ...Autómata finito Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de...

    Leer más
    1570 Palabras 7 Páginas

OTRAS TAREAS POPULARES

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS