Matematicas discretas

Solo disponible en BuenasTareas
  • Páginas : 22 (5453 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de febrero de 2011
Leer documento completo
Vista previa del texto
M´quinas de Estados Finitos a
Breve Introducci´n o Jorge Alejandro Guti´rrez Orozco e Escuela Superior de C´mputo o 15 de septiembre de 2008
Resumen Hablaremos de algunas de las m´s comunes M´quinas de Estados Fina a tos, una breve descripci´n sobre ellas, su definici´n formal y sus relacioo o nes entre ellas. En la ultima secci´n se da una sencilla definici´n de una ´ o o M´quina de Turing.Existen varios temas que se deben de conocer antes de a abordar M´quina de Turing, pero dado que la explicaci´n que se propone a o no es del todo profunda, no es necesario tener amplias bases te´ricas. El o presente va dirigido a alumnos de Nivel Superior como material de apoyo en el estudio de M´quinas de estados finitos. Se ofrece un enfoque diferente a con explicaciones sumamente sencillas.

1 Se necesitan conocimientos previos antes abordar los siguientes temas, as´ que ı explicaremos brevemente algunos conceptos que utilizaremos. Conjunto: Es un colecci´n de objetos relacionados entre ellos. Un conjunto o solo indica los elementos que lo componen, por tanto no es necesario tener un orden y no se repiten los elementos dentro de un conjunto. Un Conjunto finito es aquel donde podemoscontar sus elemntos, por ejemplo: C = {♥, ♣, ♦, ♠} claramente podemos notar que son cuatro elementos. En un Conjunto infinito encontramos de dos tipos: los Conjuntos Infinitos no Numerables donde no podemos contar todos los elementos, un buen ejemplo es el conjunto de todos los n´ meros reales ℜ y el conjunto de los u Infiniftos Numerables como el caso de los n´ meros naturales N, donde u podemosnumerar todos los elementos aunque haya un infinito de ellos. Subconjunto: Es una colecci´n de elementos que a su vez pertenece a otro o conjunto de igual o mayor n´ mero de miembros. Por ejemplo: consideu remos los conjuntos A = {a, b} y B = {z, a, c, b, d} se dice que A es un subconjunto propio de B y se escribe como A ⊂ B, si en alg´ n momento u el conjunto A pudiese llegar a tener los mismoselementos que B pero sin dejar de ser subconjunto se deber´ escribir A ⊆ B. Dos conjuntos con los a mismos elementos son iguales. S´mbolo: Es la representaci´n abstracta de un objeto, puede ser un d´ ı o ıgito o una letra. En general es cualquier caracter que nos represente alg´ n u elemento. Algunos ejemplos son: a, 1, π, etc. Alfabeto: Tambi´n llamado Vocabulario, es un conjunto finito de s´ e ımbolos.Debe existir al menos un s´ ımbolo en el alfabeto, es decir el alfabeto no puede ser un conjunto vac´ Comunmente se le denomina Σ a este ıo. conjunto. Cadena: Es una secuencia de s´ ımbolos hecha con los elementos de un Alfabeto, por eso se dice que una cadena ω sobre un alfabeto Σ es un elemento del alfabeto universal Σ∗ , es decir ω ∈ Σ∗ , donde Σ∗ es un conjunto formado de todas las posiblescadenas que se puedan hacer con los elementos de Σ. Una cadena no es un subconjunto del Alfabeto universal, es alguno de sus elementos. Una cadena no puede ser infinita. Tambi´n e se le conoce como frase o palabra. Por ejemplo consideremos un alfabeto Σ = {1, 0}, entonces Σ∗ = {1, 0, 00, 01, 10, 11, 000, ...} una cadena ω sobre Σ podr´ ser 101011010, esta cadena es un elemento de Σ∗ . ıa Lenguaje: Esun conjunto de cadenas, las cuales deben estar formadas con los s´ ımbolos de un Alfabeto Σ, entonces decimos que el Lenguaje L est´ sobre el Alfabeto Σ. Por ejemplo: el lenguaje L = {100, 001, 00, 1111} a se forma con los elemetos de Σ = {1, 0}, la cadena σ = 1010 se forma tambi´n con los elemntos de Σ (i.e. σ ∈ Σ) pero no pertenece al lenguaje e L y se denota σ ∈ L. / Estado: Es la situaci´n olas condiciones en que se halla un objeto en o alg´ n momento, dicho objeto no puede estar en m´s de un estado al mismo u a tiempo. En el caso de una m´quina son las caracter´ a ısticas que posee en un momento dado. 2

Algoritmo: Es una secuencia finita de instrucciones bien definidas. Un algoritmo est´ compuesto por una sucesi´n de pasos que llevan siempre a a o un mismo resultado. Computaci´n:...
tracking img