teoria de la computabilidad
Páginas: 2 (307 palabras)
Publicado: 25 de agosto de 2015
Unidad N° 2.
Introducción a los
Autómatas Finitos
Alfabeto
Los elementos de un alfabeto se llaman letras o símbolos.
∑ (Sigma) representa un alfabeto.
Las letras griegas minúsculas comoα (alfa) denotan símbolos o letras
del alfabeto.
Los símbolos o letra concretas se representaran por letras minúsculas
(a, b, c, …)
∈ pertenece, a ∈ ∑.
Un alfabeto se describe por laenumeración de los símbolos que
contiene ∑= {a, b, c, …, z}, ∑={1,2,3,…}
Cadena o Palabra
Se llama palabra o cadena, formada con los símbolos de un alfabeto, a
toda secuencia finita de letras de estealfabeto.
Ejemplo, juan, pedro, 123, 1234, ….
Se utilizan las ultimas letras del alfabeto habitual para representar
cadenas, x=juan o y=123.
λ (lamda) representa la cadena vacía.
Operación de concatenación (.), α.x, concatena la letra α a la cadena x.
Cadena o Palabra
Se llama longitud de una palabra o cadena a la cantidad de letra que la
componen.
Y se nombra como lacardinalidad, |abc|=3.
| λ |= 0.
∅ denota al conjunto vacío.
| ∅ |= 0.
Lenguaje
∑* se denota lenguaje universal. Representa todas la posibles palabras
que se pueden formar con elalfabeto ∑.
Se llama lenguaje sobre el alfabeto ∑ a cualquier subconjunto del
lenguaje universal.
Operaciones con lenguaje.
Unión. (+)
Concatenación. (.)
Potencia i-esima.
Clausura. Grafos
Árboles
Autómatas finitos
Arquitectura del Autómata Finito.
Autómatas finitos determinista
Un autómata finito determinista (AFD) se define como una quintupla M
= (Q,V,δ,q0,F),donde:
Q es un conjunto finito de estados.
V es el alfabeto de entrada.
q0 es el estado inicial.
F ⊆ Q es el conjunto de estados finales.
δ : Q × V −→ Q es la función de transición Función de transición del AFD.
Se puede representar de dos formas.
Mediante una tabla de transición o mediante un diagrama de transición.
Tabla de transición
δ (delta)
0
1
--> q0
q0
q1
#...
Introducción a los
Autómatas Finitos
Alfabeto
Los elementos de un alfabeto se llaman letras o símbolos.
∑ (Sigma) representa un alfabeto.
Las letras griegas minúsculas comoα (alfa) denotan símbolos o letras
del alfabeto.
Los símbolos o letra concretas se representaran por letras minúsculas
(a, b, c, …)
∈ pertenece, a ∈ ∑.
Un alfabeto se describe por laenumeración de los símbolos que
contiene ∑= {a, b, c, …, z}, ∑={1,2,3,…}
Cadena o Palabra
Se llama palabra o cadena, formada con los símbolos de un alfabeto, a
toda secuencia finita de letras de estealfabeto.
Ejemplo, juan, pedro, 123, 1234, ….
Se utilizan las ultimas letras del alfabeto habitual para representar
cadenas, x=juan o y=123.
λ (lamda) representa la cadena vacía.
Operación de concatenación (.), α.x, concatena la letra α a la cadena x.
Cadena o Palabra
Se llama longitud de una palabra o cadena a la cantidad de letra que la
componen.
Y se nombra como lacardinalidad, |abc|=3.
| λ |= 0.
∅ denota al conjunto vacío.
| ∅ |= 0.
Lenguaje
∑* se denota lenguaje universal. Representa todas la posibles palabras
que se pueden formar con elalfabeto ∑.
Se llama lenguaje sobre el alfabeto ∑ a cualquier subconjunto del
lenguaje universal.
Operaciones con lenguaje.
Unión. (+)
Concatenación. (.)
Potencia i-esima.
Clausura. Grafos
Árboles
Autómatas finitos
Arquitectura del Autómata Finito.
Autómatas finitos determinista
Un autómata finito determinista (AFD) se define como una quintupla M
= (Q,V,δ,q0,F),donde:
Q es un conjunto finito de estados.
V es el alfabeto de entrada.
q0 es el estado inicial.
F ⊆ Q es el conjunto de estados finales.
δ : Q × V −→ Q es la función de transición Función de transición del AFD.
Se puede representar de dos formas.
Mediante una tabla de transición o mediante un diagrama de transición.
Tabla de transición
δ (delta)
0
1
--> q0
q0
q1
#...
Leer documento completo
Regístrate para leer el documento completo.