= ¿Que es un Automata? =
Un automata es:
Una maquina (mecanismo) de naturaleza formal (solo existe como un mecanismo matemático). Acepta una información de entrada (input), la procesa (la somete a transformaciones simbólicas que pueden adoptar la forma de un calculo o computación) y genera un resultado o salida (output).
Definir un autómata equivaldría a definir el proceso de transformación del input en un output, lo que equivale a definir una función cuyos argumentos son el input y cuyo valor es el output
= TIPOS DE AUTOMATAS =
Hay muchos tipos de autómatas, cada tipo de autómata se asocia a una potencia computacional determinada, es decir a una capacidad dada de resolución de problemas, de hecho, podemos clasificar los problemas algorítmicamente solubles asociándolos al tipo de autómata que resuelve
Estos tipos se ordenan en jerarquía de menor a mayor potencial computacional
· Jerarquía de autómatas:
>Autómatas finitos (Redes Lógicas)
>Autómatas intermedios:
- Autómatas de memoria de pila
-Autómatas de memoria linealmente limitada
>Maquinas de Turing
= TIPOS DE AUTOMATAS =
· Además, podemos clasificar los autómatas:
Por el tipo de proceso que ejecutan
Aceptación o reconocimiento
Generación
Por su tipo de causalidad:
Determinista
No – Determinista
Por el tipo de su almacenamiento de información:
De tamaño fijo
De tamaño creciente
De tamaño infinito
Por el tipo de la información que manejan
Discreta
Continua
= TIPOS DE AUTOMATAS =
· Autómatas aceptadores o reconocedores:
Resuelven problemas con respuestas si- no que se modeliza normalmente como la identificación de dos estados finales uno de aceptación y otro de rechazo.
· Autómatas generadores o transductores:
Construyen una respuesta específica (una salida) para el problema planteado
· Autómatas determinista:
La solución del problema viene unívocamente determinada por las entradas y los estados internos del autómata
· Autómatas no-deterministas:
La respuesta no esta unívocamente determinada
= NOCIONES MATEMÁTICAS =
Para el desarrollo de los autómatas debemos tener en cuenta las nociones matemáticas, esto se refiere a como manejaremos la información de la cual estará constituida los autómatas, haciendo referencia a los números como a las letras, es decir el alfabeto que constituirá a nuestro autómata.
= CONJUNTOS =
¿Que es un conjunto?
Un conjunto es una colección de objetos llamados elementos del conjunto.
Si A es un conjunto y a es un elemento de A utilizaremos la notación a Î A (se lee “a es un elemento de A”). Se usa la notación b Ï A cuando b no es un elemento de A.
Si A contiene exactamente los elementos a1, a2, . . . . ., an, lo indicamos escribiendo A={a1,a2, . . . . ., an}.
Un conjunto solo se caracteriza por sus elementos y no por el orden en el cual se listan.
Los conjuntos A y B son iguales si contienen los mismos elementos. Por lo tanto si, A={1,2,3} y B={2,1,3} se puede escribir que A=B.
Algunas veces es conveniente describir el contenido de un conjunto en términos de un propiedad que sea característica de todos los elementos del conjunto. Sea P(x) una proposición sobre x. La notación {x½ P(x)}, que se interpreta como “ el conjunto de todas las x tales que P(x) ”, denota el conjunto de todos los x para los cuales P(x) es una proposición verdadera. (Todas las x tienen la propiedad P).
Notación de Conjuntos
P = { x | P(x)}. See lee “x tal que P(x) es verdadero”.
A= { x | x es una letra del alfabeto}.
A= { a, b, c, d, e, . . . . . . . . . z}.
Los conjuntos se representan de dos formas:
Por extensión ® A={a, b, c, d, e, f, g, h, i, j, k, l, m, n, ñ, o, p, q, r, s, . . . . . . . . . . . . }
Por comprensión ® A={x | x es una letra del alfabeto}
Conjunto Finito
A={a, b, c, d, e, f, g, h, i, j, k, l, m, n, ñ, o, p, q, r, s, t, u, w, x, y, z }
Conjunto Infinito
B={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, . . . . . . . . . . . . . . . . . . . . }
= OPERACIONES CON CONJUNTOS=
Las operaciones habituales que se definen sobre los conjuntos son:
El conjunto 0 llamado conjunto vacío o nulo, no tiene elementos. El conjunto vació es un subconjunto de todos los conjuntos.
La unión de conjuntos A y B se denota por A È B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos.
Por lo tanto A È B={x½x Î A o x Î B}.
Por ejemplo, si A={1,2,3} y B={a,b}, entonces A È B={1,2,3,a,b}.
La intersección de A y B es el conjunto de todos los elementos que aparecen simultáneamente en A y también en B.
Por lo tanto A Ç B={x½x Î A y x Î B}.
Por ejemplo, si A={1,4,5,7} y B={2,4,7,8}, entonces A Ç B={4,7}.
El complemento relativo si Ay B son dos conjuntos cualesquiera, el complemento de B con respecto a A es el conjunto: A-B={ x½x Î A y x Î B}.
Por lo tanto, A-B esta compuesto por todos los elementos de A que no están también, en B. Por ejemplo, si A={0,2,4,6,8,10} y B={0,1,2,3,4}, entonces A-B=[6.8.10}, mientras que B-A={1,3}.
|
2^A , el conjunto de potencia de A, es el conjunto formado por todos los
|
Por ejemplo, si A={a,b,c}. Entonces 2 ={ o, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}.
Dados dos conjuntos A y B, su producto cartesiano, AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene de A y el segundo de B. Así que, AxB={(a,b)ç aÎA y bÎB}. Por ejemplo, si A={1,2,3} y B{5,6} entonces: AxB={(1,5), (2,5), (3,5), (1,6), (2,6), (3,6)}.
Si A y B son conjuntos y todos los elementos de A son también elementos de B, se escribe A Í B y se dice que A es un subconjunto de B.
Por ejemplo A={1,2,3} y B={0,1,2,3,4,5}, se tiene A Í B. Por otro lado B no es un subconjunto de A, porque los elementos 0,4 y 5 de B no lo son de A.
Ejemplo:
C ={Frutas}
|
S Í C <=> Y x| x Î S = >X Î C
Se lee: S es un subconjunto de C o S esta incluido en C si para todo x
|
La inclusión cuando cualquier elemento de A que este en B, o cualquier elemento de B que este en A, o que sean iguales. Por ejemplo si A={2,4,5,7,8} y B={2,4}, entonces B Ì A={2,4}.
La cardinalidad de un conjunto es el numero de elementos de ese conjunto. Por ejemplo si A={a,b} entonces | A | = 2. la cardinalidad del conjunto vació es 0 porque no tiene ningún elemento.
Todos los conjuntos aquí tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. Si A es un conjunto, entonces U-A es el conjunto de todos los elementos que no están en A. Conviene denotar tales complementos mediante A, de forma que U-A=A. Obsérvese que 0=U y U=0.
= ALFABETOS ( å ) =
Un alfabeto es un conjunto no vació y finito de símbolos. En el caso del alfabeto ingles, la colección definida es el conjunto de las letras del alfabeto junto con los símbolos que se usan para construir palabras en ingles (tales como el guión, el apostrofe y otros por el estilo).
Cada símbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vacía, la cual se denota por el símboloå, es una palabra sobre cualquier alfabeto.
= PROPIEDADES DE LAS CADENAS O “STRINGS” =
Una cadena (o palabra) es una secuencia finita de símbolo. Por ejemplo: a, b y c son símbolos y abcd es una cadena.
= Cadena Vacía
La cadena vacía, denotada por ג, es la cadena que consiste en cero símbolos. Por tanto, tiene longitud |ג| = 0.
= Longitud
Si w es una cadena sobre cualquier alfabeto, su longitud se denota como | w |. La longitud de w es el número de símbolos que tiene la cadena. Por ejemplo: abcd tiene longitud | w | = 4.
= Concatenación
La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo: si w=“banana” y z=”rama”, la concatenación de w con z es la cadena “bananarama”. La concatenación de las cadenas w y z se denota como wz o w.z.
La cadena vacía es la identidad para el operador de concatenación. Es decir, å = w å = z x = å para cada cadena x=casa z = ג (vacío) w = roja .
|
|
W = ג
|
W = 122
|
W = 122122
|
W = 122122122
= Igualdad de Cadenas
Si w y z son cadenas, se dice que w es igual a z, si tienen la misma longitud y los mismos símbolos en la misma posición. Se denota mediante w = z.
= Prefijo
Los prefijos de un cadena esta formados por los primeros símbolos de esta. Por ejemplo, la cadena 121 sus prefijos son: ג , 1, 12, y 121 con lo que toda palabra puede considerarse prefijo de si misma. Un prefijo de una cadena que no sea la misma cadena es u prefijo propio.
= Sufijo
Los sufijos de una cadena están formados por los últimos símbolos de esta. Por ejemplo, la cadena abc sus sufijos son: ג, c, bc, abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio.
= Subcadena.
Una cadena w es una subcadena o subpalabra de otra cadena z, si existen las cadena x o y para las cuales z = xwy.
= Transpuestas =
La inversa o transpuesta de una cadena w es la imagen refleja de w. Por ejemplo, si w = “able” entonces su inversa es “elba”. Para denotar la inversa de w se usa w`.
No hay comentarios.:
Publicar un comentario