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 estadofinito ´ 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 delas maquinas de estado finito es el reconocimiento de lenguajes (vital para el ˜ ´ diseno y construccion de compiladores). ´ ˜ Entre las maquinas de estado finito disenadas especialmente ´ ´ para elreconocimiento de lenguajes, estan los automatas de ´ estado finito (maquinas de estado finito sin salida).

Contenido

´ Automatas de estado finito ´ Concatenacion de conjuntos de cadenas Clausura deKleene ´ Automatas de estado finito deterministas ´ Automatas de estado finito no deterministas

´ Concatenacion de conjuntos de cadenas

´ Concatenacion
Suponga que A y B son subconjuntos de V ∗, donde V es un ´ vocabulario. La concatenacion de A y B, denotado AB, es el conjunto de todas las cadenas de la forma xy donde x es una cadena de A y y es una cadena de B. Ejemplo1: Sean A = {0, 11}y B = {1, 10, 110}. AB = {01, 010, 0110, 111, 1110, 11110} y BA = {10, 111, 100, 1011, 1100, 11011}. Luego AB = BA

´ Concatenacion de conjuntos de cadenas (2)

´ ´ De la definicion deconcatenacion de 2 conjuntos de cadenas, n , para n = 0, 1, . . . recursivamente como: podemos definir A A0 = {λ} An+1 = An A

Ejemplo1: Sean A = {1, 00} A0 = {λ} A1 = A0 A = {λ}{1, 00} = {1, 00} A2 = A1 A ={1, 00}{1, 00} = {11, 100, 001, 0000} A3 = A2 A = {11, 100, 001, 0000}{1, 00} = {111, 1100, 100110000, 0011, 00100, 00001, 000000}

Contenido

´ Automatas de estado finito ´ Concatenacion deconjuntos de cadenas Clausura de Kleene ´ Automatas de estado finito deterministas ´ Automatas de estado finito no deterministas

Clausura de Kleene
(En honor a Stephen Cole Kleene) Suponga que A es...