Introduccion maquinas de estado fini

Vista previa del material en texto

TEMA : INTRODUCCION MAQUINA DE ESTADO 
FINITO
Universidad Nacional de Ingeniería
Facultad de Ingeniería Industrial y de Sistemas
Alfabeto
Definición.- Un alfabeto es un conjunto finito de símbolos. El símbolo es un primitivo de 
la teoría de los lenguajes formales y para representarlos se suelen utilizar o bien las 
primeras letras del alfabeto latino o bien dígitos. Por tanto, cualquiera de los conjuntos 
siguientes es un alfabeto:
B = {0,1}. Alfabeto binario
A= {a, b, c,…….z} conjunto de todas las letras minúsculas 
El conjunto de todos los caracteres ASCII
Palabra
Definición.- Una palabra sobre el alfabeto 𝐴 es una sucesión finita de elementos de 𝐴.
Es decir 𝑢 es una palabra sobre 𝐴, si y solo si 𝑢 = 𝑎1………𝑎𝑛 donde 𝑎𝑖 ∈ 𝐴, ∀𝑖 = 1… . 𝑛
Ejemplo
Sea 𝐴 = 0,1 , entonces 00111 es una palabra sobre este alfabeto.
Cadena de caracteres
Una cadena de caracteres (que también se denomina en ocasiones palabra) es una 
secuencia finita de símbolos seleccionados de algún alfabeto. 
Por ejemplo, 01101 es una cadena del alfabeto binario B = {0,1}. La cadena 111 es otra 
cadena de dicho alfabeto.
La cadena vacía 
La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena, 
designada por ε, es una cadena que puede construirse en cualquier alfabeto.
La cadena vacía es el elemento de identidad de la operación de concatenación, de tal modo que
ε ⊕ aaabbb = aaabbb
La operación de concatenación de cadenas no es conmutativa
(pero sí asociativa); por tanto aaabbb ⊕ ab ≠ ab ⊕ aaabbb.
Clausura sobre el alfabeto A
Definición.- La clausura del alfabeto 𝐴 denotado por 𝐴∗, el conjunto de todas las
palabras sobre un alfabeto 𝐴, también llamado clausura de kleene.
𝐴∗ =∪ 𝐴𝑖 , 𝑖 = 1,2,3…… . .
Donde 𝐴𝑖 es el conjunto de todas las cadenas de longitud 𝑖 sobre el alfabeto A
Ejemplo
Sea el alfabeto 𝐵 = 0,1 , calcular 𝐵∗
𝐵0 = 𝜀
𝐵1 = 0,1
𝐵2 = 00,01,10,11
𝐵3 = 000,001,010,011,100,101,110,111
.
.
Luego 𝐵∗ = 𝐵0 ∪ 𝐵1 ∪ 𝐵2 ∪ 𝐵3 ∪⋯ = ε, 0,1,00,01,10,11000,001,010,011,100,101,110,111…
Longitud de una cadena 
Definición.- La longitud de la palabra o cadena 𝑢 es el número de símbolos que
contiene 𝑢 y se denota por 𝑢 , es decir si 𝑎1……… . 𝑎𝑛 entonces 𝑢 = 𝑛
Por ejemplo,|011|= 3y| ε |= 0.
Igualdad de cadenas
Dos cadenas son 𝐿1 𝑦 𝐿2, son iguales si se cumple 𝐿1 = 𝐿2 𝑦 ∀𝑖: 1 ≤ 𝑖 ≤ 𝑛: 𝑎𝑖 = 𝑏𝑖
Reversa de una cadena 
Sea la cadena 𝐿1 = 𝑎1……… . 𝑎𝑛, su reversa denotada por 𝐿1
𝑅, estará dado por
𝐿1
𝑅 = 𝑎𝑛 ……… . 𝑎1
Lenguaje
Definición.- Un lenguaje es un conjunto finito o infinito de cadenas.
Por tanto los conjuntos siguientes son, lenguajes:
i) L1 = {ε, ab, aabb, aaabbb} L2 = {001, 011,111}.
ii) 𝐿0 = ∅ lenguaje finito vacío
Definición.- (Teoría de lenguajes formales). La Teoría de los lenguajes formales 
estudia los lenguajes prestando atención únicamente a sus propiedades 
estructurales, definiendo clases de complejidad estructural y estableciendo 
relaciones entre las diferentes clases
Definición.- (Teoría de la complejidad computacional). La Teoría de la complejidad 
computacional estudia los lenguajes prestando atención a los recursos que utilizaría un 
dispositivo mecánico para completar un procedimiento de decisión, definiendo así 
diferentes clases de complejidad computacional y las relaciones que existen entre ellas.
Concatenación de cadenas
Sean 𝑥 e 𝑦 dos cadenas. Entonces, 𝑥𝑦 denota la concatenación de x e y, es decir, la
cadena formada por una copia de x seguida de una copia de y. Dicho de manera más
precisa, si x es la cadena compuesta por 𝑖 símbolos 𝑥 = 𝑎1𝑎2… . . 𝑎𝑖 , y es la cadena
compuesta por j símbolos y 𝑦 = 𝑏1𝑏2… . . 𝑏𝑗, entonces 𝑥𝑦 es la cadena de longitud i+ j
es dada por: 𝑥𝑦 = 𝑎1𝑎2… . . 𝑎𝑖𝑏1𝑏2… . . 𝑏𝑗.
Además operación de concatenación de los lenguajes 𝐿1 𝑦 𝐿2 está definido por
𝐿1. 𝐿2 = 𝑤1. 𝑤2 ∈ 𝐴
∗/𝑤 ∈ 𝐿1 𝑦 𝑤 ∈ 𝐿2 , donde de acuerdo a lo definido se omite el punto.
Propiedades de concatenación
a) 𝐿1. 𝐿2 es una cadena sobre el alfabeto 𝐴
b) 𝐿1. 𝜀 = 𝜀𝐿1 = 𝐿1
c) 𝐿1. 𝐿2 = 𝐿1 + 𝐿1
d) 𝐿1. 𝐿2 ≠ 𝐿2. 𝐿1 , no es conmutativa (puede suceder en algunos
casos)
e) 𝐿1. 𝐿1 = 𝐿1
2(potencia cuadrada de la cadena 𝐿1)
f) 𝐿1. 𝐿1. 𝐿1. 𝐿1… .= 𝐿1
𝑘potencia k-esima de la cadena 𝐿1
.
.
.
𝐿𝑘 = 𝐿1. 𝐿1. 𝐿1. 𝐿1………𝐿1 (k-veces)
𝐿0 = 𝜀
𝐿1 = 𝐿1
𝐿2 = 𝐿1. 𝐿1
Lenguajes regulares
Los lenguajes regulares sobre un alfabeto dado 𝐴 son todos los lenguajes que se
pueden formar a partir de los lenguajes básicos 0, {𝜀}, {a} 𝑎 ∈ 𝐴 , por medio de
las operaciones de unión, concatenación y estrella de Kleene (clausura de 𝐴)
Operaciones con lenguajes 
Sean dos lenguajes 𝐿1 𝑦 𝐿2, sobre 𝐴, donde 𝐿1 ⊆ 𝐴
∗, 𝑦 𝐿2 ⊆ 𝐴
∗ y se define las operaciones
de unión, intersección, diferencia y complemento entre los lenguajes 𝐿1 𝑦 𝐿2 de la siguiente
forma.
a) 𝐿1 ∪ 𝐿2 = 𝑤 ∈ 𝐴
∗/𝑤 ∈ 𝐿1 𝑜 𝑤 ∈ 𝐿2
b) 𝐿1 ∩ 𝐿2 = 𝑤 ∈ 𝐴
∗/𝑤 ∈ 𝐿1 𝑦 𝑤 ∈ 𝐿2
c) 𝐿1 − 𝐿2 = 𝑤 ∈ 𝐴
∗/𝑤 ∈ 𝐿1 𝑦 𝑤 ∉ 𝐿2
d) 𝐿1 = 𝑤 ∈ 𝐴
∗/ 𝑤 ∉ 𝐿1 = 𝐴
∗ − 𝐿1
Ejemplo
Sean 𝐿1, 𝐿2 los lenguajes sobre el alfabeto 𝐴 = 𝑎, 𝑏, 𝑐 definido por
𝐿1 = 𝑎
𝑖𝑏𝑗𝑐𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0 , 𝐿2 = 𝑎
𝑖𝑐2𝑖 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑖 ≥ 0
Calcular
a) 𝐿1 ∪ 𝐿2 c) 𝐿1 − 𝐿2 d) 𝐿1
b) 𝐿1 ∩ 𝐿2
Solución
a) 𝐿1 ∪ 𝐿2 = 𝐿1 = 𝑎
𝑖𝑏𝑗𝑐𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0
b) 𝐿1 ∩ 𝐿2 = 𝑎
𝑖𝑐2𝑖 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑖 ≥ 0
c) 𝐿1 − 𝐿2 = 𝑎
𝑖𝑏𝑗𝑐𝑞 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖 ≥ 0, 𝑗 > 0
e) 𝐿1 = 𝑤 𝑡𝑎𝑙𝑞𝑢𝑒 𝑤 ∈ 𝐴
∗, 𝑦 𝑤 ≠ 𝑎𝑖𝑏𝑗𝑐𝑞𝑦 𝑞 = 2𝑖 + 𝑗 𝑦 𝑖, 𝑗 ≥ 0
Estado de una maquina 
Definición.- La condición interna completa de la máquina y de toda su memoria en 
un instante particular, constituye el estado de la maquina en ese instante.
Máquinas de estado finito
Una máquina de estados finitos en un modelo abstracto para la manipulación de símbolos, nos
permiten saber si una cadena pertenece a un lenguaje o nos pueden generar otro conjunto de
símbolos como resultado.
Es un modelo matemático de una maquina con memoria que tiene un conjunto de 
estados (valores internos), que puede recibir símbolos de entrada y obtener símbolos 
de salida
Una máquina de estado finito M es dado por 𝑀 = 𝑆, 𝐼, 𝑂, 𝑓, 𝑔, 𝑆0 , donde
I= {conjunto de entradas finito (símbolos de entrada) o vocabulario de entrada}
O= {conjunto de salidas finito (símbolos de salida) o vocabulario de salida}
S= {conjunto de estados (finitos)}
S0 = {estado inicial}
𝑓: 𝐼𝑥𝑆 → 𝑆 , es la función de transición o función de estado siguiente y para un par del
conjunto 𝐼𝑥𝑆 devuelve un estado perteneciente al conjunto 𝑆
𝑔: 𝐼𝑥𝑆 → 𝑂, es la función de salida y para un par del conjunto 𝐼𝑥𝑆 devuelve un símbolo
de salida del conjunto 𝑂