Automatas finitos deterministicos y no deterministicos

Unidad 2. Lenguajes regulares

Índice de contenido

| | Pag |
Unidad 2 | Lenguajes regulares | |
| 2.1. | Autómatas finitos | 3 |
| | 2.1.1. | Autómatas finitos determinísticos | 4 |
| | | 2.1.1.1. | Palabras aceptadas | 6 |
| | 2.1.2. | Autómatas finitos no determinísticos | 10 |
| | | 2.1.2.1. | Autómata finito no determinístico con movimiento de cadena vacía |13 |
| | | 2.1.2.2. | Conversión de un AFN a un AFD | 17 |
| 2.2. | Expresiones regulares | 23 |
| | 2.2.1. | Algoritmo | 24 |
| 2.3. | Lenguajes no regulares | 35 |
| | 2.3.1. | Abreviaturas en la notación | 42 |
| | 2.3.2. | Leyes algebraicas para expresiones regulares | 43 |
| | 2.3.3. | Conjuntos no regulares | 44 |
| | | | | |
| Ejercicios | 45 |
| |2.1. | Autómatas finitos | 45 |
| | | 2.1.1. | Autómatas finitos determinísticos (AFD) | 45 |
| | | 2.1.2. | Autómatas finitos no determinísticos (AFN) | 48 |
| | 2.2. | Expresiones regulares | 50 |
| | 2.3. | Lenguajes no regulares | 50 |

Unidad 2
Lenguajes regulares

2.1. Autómatas finitos.

Un autómata finito o máquina de estado finito es un modelo matemático de unsistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Condiciones de estado de transición
Estado
Condiciones de salida
INPUTS
OUTPUTS

Fig. 2.1. Esquema lógico de un autómata finito

Definición formal: Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde:
* Sun conjunto de estados;
* Σ es un alfabeto;
* T es la función de transición: ;
* es el estado inicial;
* es un conjunto de estados de aceptación o finales.
Ejemplo 2.1-1:
* S = {S1, S2},
* Σ = {0,1},
* T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
* s = S1
* A = {S1}.

2.1.1. Autómatas finitos determinísticos.


Como se manifestóanteriormente,un autómata finito consiste en un conjunto finito de estados y un conjunto de transiciones de estado a estado que se dan sobre símbolos de entrada tomados de algún alfabeto sigma (Σ).
Ahora bien, un Autómata finito es determinísticosi para cada símbolo de entrada existe exactamente una transición a partir de cada estado.
A continuación se muestra un AFD y su definición formal, esdecir, la especificación de los 5 elementos que lo integran: estados (Q), alfabeto (Σ), estado inicial (S), estados de aceptación (F) y su función de transición representada en una matriz.

q0
q1
b
a
a
b
q2
b
a

Q = {q0,q1,q2} | Representa el conjunto de los 3 estados que forman al autómata. |
Σ = {a,b} | Se observa que las transiciones entre estados están etiquetadas con a y conb, este será nuestro alfabeto. |
S = q0 | El estado de inicio es q0. Se identifica por la flecha que lo señala, el estado inicial pertenece al conjunto de estados, es decir: S Є Q |
F = {q1,q2} | Los estados finales o de aceptación son q1 y q2, se identifican por los círculos de doble trazo. El conjunto de estados de aceptación es un subconjunto del conjunto de estados, es decir: F C Q |
q2q3
q1
q0
q4
0
1
1
1
1
0

La Función de Transición señala los cambios de estado para cada símbolo del alfabeto, es decir, dado un estado y un carácter indica el próximo estado.

S: KxΣ → K
| a | b |
q0 | q1 | q2 |
q1 | q1 | q1 |
q2 | q0 | q2 |

Ejercicio 2.1.1-1:Dado el siguiente AFD encontrar su definición formal:

q1
q0
1
0
1
0
1
0
q2
q3
1
0

Solución:
K ={q0,q1,q2,q3}
Σ = {1,0}
S = q0
F = {q0}
δ: K x Σ → K
| 0 | 1 |
q0 | q2 | q1 |
q1 | q3 | q0 |
q2 | q0 | q3 |
q3 | q1 | q2 |

Otra manera de escribir la función de transición es con la siguiente notación:

δ = { ((q0,0),q2) , ((q0,1),q1) , ((q1,0),q3) , ((q1,1),q0) , ((q2,0),q0) , ((q2,1),q3) , ((q3,0),q1) , ((q3,1),q2)}

2.1.2.1. Palabras aceptadas

Un AF...