TAREAS (INVESTIGACIÓN)

Lenguajes Regulares 

Los lenguajes regulares se llaman así porque sus palabras contienen regularidades"o repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1siguiente:L1 = {ab, abab, ababab, abababab, . . .} 

Las ER son simplemente formulas cuyo propósito es representar cada una de ellas un lenguaje. 

GRAMÁTICA

Una gramática es un conjunto de reglas para formar correctamente las frases de un lenguaje; así tenemos la gramática del español, del francés, etc. Una regla es una expresión de la forma α → β, en donde tanto α como β son cadenas de símbolos en donde pueden aparecer tanto elementos del alfabetoΣ como unos nuevos símbolos, llamados variables. Los símbolos que no son variables son constantes.  

UNIDAD 3

Autómatas finitos;

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados finito, una función de transición, un estado inicial y un conjunto de estados finales.

   Tipos;

• Autómata finito determinista

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

En un AFD no pueden darse ninguno de estos dos casos:

• Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q, ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

Un tipo interesante de autómatas finitos deterministas son los llamados acíclicos y un ejemplo de éstos son los tries.

Tries; un trie es una estructura de datos de tipo árbol que permite la recuperación de información (de ahí su nombre del inglés reTRIEval). 

• Autómata finito no determinista

Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:

• Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
• Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.

Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su función de transición. Mientras en un AFD esta función se define de la siguiente manera:

{\displaystyle \delta :Q\times \Sigma \to Q}

en un AFND se define como:

{\displaystyle \delta :Q\times \Sigma \to {\mathcal {P}}(Q)}

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

{\displaystyle \delta :Q\times \{\Sigma \cup \epsilon \}\to {\mathcal {P}}(Q)}

donde P(Q) es el conjunto potencia de Q.

autores; Michael Oser Rabin (  Rabin, Michael O.),  Stephen Wolfram (https://es.wikipedia.org/wiki/Stephen_Wolfram)

3 Ejercicios AFD.

Ejercicio 1: Obtenga un AFD dado el siguiente lenguaje definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que inician en "0". 

SOLUCIÓN  

Ejercicio 2:  Obtenga un AFD dado el siguiente lenguaje definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que terminan en "1". 

SOLUCIÓN   

Ejercicio 3: Obtenga un AFD dado el siguiente lenguaje definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que contienen a la sub-cadena "01".

SOLUCIÓN 

CONVERSION AFD-AFND

Transformación de autómata finito no determinista a autómata finito determinista. Todo AFND estricto, o sea un AFND que no es AFND-V, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.

Este algoritmo aunque siempre obtiene un AFD equivalente no puede decirse que sea la versión minimal del mismo, para ello deben aplicarse otras transformaciones.

Algoritmo

Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q0>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones ó (léase: del estado qi mediante el terminal x se va a qj), F son los estados finales o de llegada dentro de Q, q0 es el estado inicial o de partida

1. A se transforma en AAFD=<QA,T, gA,FA,q0A>', tal que:
   1. VA=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.
   2. FA={x | }.
   3. gA={<r,x,q> | }.
   4. q0A={q0}.
2. Luego se eliminan de AAFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q0A.

Ejemplo

Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>, que reconoce a las cadenas de as y bs que comienzan con cualquiera cantidad de estas letras y terminan forzosamente en ab. El siguiente puede ser su diagrama de estados:

Primero se obtiene autómata derivado AAFD=<VAFD,TAFD,gAFD,FAFD,{q0}> a partir del conjunto potencia de los estados de A donde:

• VAFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.
• TAFD={a,b}.
• FAFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.

Cuyo diagrama sería:

Luego se retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f}, determinados mediante la clausura de {q0}, y queda:

AAFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1},a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{ {q0,f} },{q0}}.

AUTÓMATAS DE PILA

Un autómata con pila, autómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. 

UNIDAD 4

Analizador léxico
Lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa la secuencia de caracteres en unidades con significado propio (componentes léxicos o tokens)Las palabras clave identificadores, operadores, constantes numéricas, signos de puntuación como separadores de sentencia, llaves, parestesias, etcétera. son diversas clasificaciones de componentes léxicos. 

Representación de un Analizador léxicoLos componentes léxicos se representan:1. Palabras reservadas: if, while, do, ...2. Identificadores: variables, funciones, tipos definidos por el usuario, etiquetas, ...3. Operadores: =, >, <, >=, <=, +, *, ...4. Símbolos especiales: ;, ( ), { }, ...5. Constantes numéricas. literales que representan valores enteros y flotantes.
6. Constantes de carácter: literales que representan cadenas de caracteres. 

¿Qué es un analizador léxico?

Se encarga de buscar los componentes léxicos o palabras que componen el programa fuente, según unas reglas o patrones. La entrada del analizador léxico podemos definirla como una secuencia de caracteres.El analizador léxico tiene que dividir la secuencia de caracteres en palabras con significado propio y después convertirlo a una secuencia de terminales desde el punto de vista del analizador sintáctico, que es la entrada del analizador sintáctico. El analizador léxico reconoce las palabras en función de una gramática regular de manera que sus NO TERMINALES se convierten en los elementos de entrada de fases posteriores.
Ejemplos: 

Análisis sintáctico 

determina si la secuencia de componentes léxicos sigue la sintaxis del lenguaje y obtiene la estructura jerárquica del programa en forma de árbol, donde los nodos son las construcciones de alto nivel del lenguaje.Se determina las relaciones estructurales entre los componentes léxicos esto es semejante a realizar el análisis gramatical sobre una fase en el lenguaje natural. La estructura sintáctica se define mediante las gramáticas independientes del contexto.

¿Qué es el analizador sintáctico?

Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico. En la práctica, el analizador sintáctico también hace:

• Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).

• Chequeo de tipos (del analizador semántico).

• Generar código intermedio.

• Generar errores cuando se producen. En definitiva, realiza casi todas las operaciones de la compilación. 

Análisis Semántico

El análisis semántico dota de un significado coherente a lo que hemos hecho en el análisis sintáctico.El chequeo semántico se encarga de que los tipos que intervienen en las expresiones sean compatibles o que los parámetros reales de una función sean coherentes con los parámetros formales
Funciones principales

Identificar cada tipo de instrucción y sus componentes

Completar la Tabla de Símbolos

Realizar distintas comprobaciones y validaciones:

Comprobaciones de tipos.

Comprobaciones del flujo de control.

Comprobaciones de unicidad. 

UNIDAD 6

MAQUINA DE TURING

La llamada "Máquina de Turing" es en realidad un modelo matemático consistente en un autómata que es capaz de "implementar cualquier problema matemático expresado a través de un algoritmo". A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor. 

Como su propio nombre indica, la máquina de Turing fue creada por el matemático inglés Alan Turing, un genio en muchos campos pero especialmente en la criptografía y la lógica. Originalmente la denominó "Máquina de Computación Lógica" siendo una de las mayores aportaciones pues despejó el camino de la ciencia de la Computación, de la Informática moderna.

Una Máquina de Turing consta de una cinta infinita dividida en espacios de trabajo o celdas yuxtapuestas que actúa como memoria, un cabezal capaz de leer y escribir símbolos en la cinta y moverla de celda en celda a derecha e izquierda, un registro de estado, y una tabla finita de instrucciones o tabla de acción.

La máquina de Turing es considerada un autómata con la capacidad de reconocer lenguajes formales de acuerdo a la jerarquía de Chomsky, razón por la cual es muy superior a otros autómatas como el autómata con pila o el autómata finito.

Existen diversos tipos de máquinas de Turing: con movimiento stay o "esperar", con cinta infinita a ambos lados, con cinta multipista, multicinta, determinista y no determinista, la Máquina de Turing Cuántica. En resumen, una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT, ambos formados por un código binario de unos y ceros.

TRANSICIONES

Fuente de informacion: https://formatalent.com/que-es-una-maquina-de-turing-y-como-funciona/

DAVID HILBERT

A finales del siglo XIX y en la primera mitad del XX, hubo diversos intentos de formalizar y sistematizar las denominadas 'ciencias puras'. Con respecto a las matemáticas, en su obra de 1899, Grundlagen der Geometrie, David Hilbert (1862-1943) plantea ya algunas de las ideas de lo que, desde entonces, irá consolidándose como su formalismo o teoría de la demostración. Ciertas partes 'esenciales' de la matemática -geometría, aritmética, topología, etc.- deben tratarse en un lenguaje formal a partir de unos axiomas 'ad hoc' que son los que configuran los objetos de la teoría y las interrelaciones que coexisten entre ellos. De hecho, los 'objetos semánticos' que se amagan detrás de los 'objetos formales' carecen de importancia: "No importa si se trata de puntos, rectas, planos o de mesas, sillas o jarras de cerveza". Aparece aquí, agazapada, la distinción entre 'teoría formal' y 'matemática formalizada'.

referencias; Hilbert, David (1899). Grundlagen der Geometrie. Teubner: Sttugart. 

fuente de informacion: https://blogs.elpais.com/turing/2013/02/algunos-vinculos-entre-los-teoremas-de-godel-y-turing.html

KURT GODEL

Partamos presentando a nuestros dos protagonistas. Kurt Gödel (1906-1978) fue un matemático austríaco que hoy es considerado el lógico más relevante desde Aristóteles. Muy joven se interesó por la lógica y los fundamentos de las matemáticas. En 1931, cuando tenía 25 años, publicó su trabajo sobre la incompletitud de los sistemas formales que cambiaría para siempre nuestro entendimiento de los sistemas formales y la lógica. Gödel era una persona muy reservada, profunda y obsesiva (en su infancia su familia le apodaba "Señor Por qué"). Hay una anécdota que muestra muy bien su carácter.

Al llegar a Estados Unidos arrancando del nazismo que había anexado Austria, para nacionalizarse debió estudiar la constitución de los Estados Unidos. Detallista, descubrió que este entramado lógico-legal permitiría una dictadura como la nazi. Sus amigos Einstein y Morgenstern intentaron desesperadamente convencerlo que no mencione eso en público, que era un caso muy poco probable de darse. Durante el examen de inmigración, apareció el tema de las formas de gobierno y Gödel orgulloso le indica al examinador que tiene una demostración de la posibilidad de una dictadura.

ALONSO CHURCH

Todos dejaron huellas imborrables pero Turing es más conocido por lo anecdótico de su vida que por el legado de imperecedera impronta: el teorema de Church-Turing. Sin ser secundarios sus otros logros -en criptografía, durante la Segunda Guerra Mundial; en la concepción del primer ordenador programable; su contribución seminal al nacimiento de la Inteligencia Artificial; sus estudios de morfogénesis- lo verdaderamente insuperable, por así decir, fue su respuesta -negativa, después de Alonzo Church pero independientemente de él- al "problema de la decibilidad": ¿Existe un método o algoritmo que permite decidir si una proposición o fórmula es verdadera o falsa? Turing realizó un doblete, en un solo artículo, que no tiene prácticamente parangón. Fue capaz de responder simultáneamente a uno de los tres problemas más profundos de lógica-matemática -quedó dicho, el problema de la decibilidad- y concebir el fundamento teórico de los ordenadores modernos.

TEST DE TURING

El test de Turing (o prueba de Turing) es una prueba de la habilidad de una máquina para exhibir un comportamiento inteligente similar al de un ser humano de tal manera que, interactuando con ella en una conversación, una persona pueda determinar si su interlocutor es una máquina o una persona. 

Desde su postulación por parte de Alan Turing, la prueba se ha convertido en la vara con la que científicos y desarrolladores miden los avances que, en materia de Inteligencia Artificial, hemos venido desde hace unos 30 años pero que se han disparado en los últimos 3.

La idea es que si luego de 5 minutos de conversación (el experimento original estaba pensado para conversaciones de texto) el humano no puede decir con certeza si su interlocutor es una máquina o una persona, la máquina pasó el test.

fuente de informacion: https://techcetera.co/que-es-el-test-de-turing/

MÁQUINAS DE TURING 

La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.

(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

COMPUTACIÓN CON MEMBRANA Y SISTEMAS P.

Un sistema P es un computacional modelo en el campo de la informática que realiza cálculos utilizando un proceso inspirado biológicamente. Se basan en la estructura de biológicos células , haciendo abstracción de la forma en que los productos químicos interactúan y transversales de las membranas celulares . El concepto fue introducido por primera vez en un informe de 1998 por el científico de la computación Gheorghe Păun , cuyo apellido es el origen de la letra P en 'P Systems. Variaciones sobre el modelo del sistema P llevaron a la formación de una rama de investigación conocido como ' computación membrana .'

Aunque inspirado por la biología, el interés de la investigación primaria en sistemas de P se refiere a su uso como un modelo computacional, en lugar de para el modelado biológico , aunque esto también está siendo investigado.

                                                                   fuente de informacion: https://es.qwe.wiki/wiki/P_system

COMPUTACIÓN CON ADN

Leonard Adleman, de la Universidad del Sur de California inició el estudio en este campo, en 19941​. Adleman probó la utilidad, al menos teórica, del uso del ADN para resolver problemas. En particular, logró resolver el Problema del camino Hamiltoniano de 7 nodos. Desde los primeros experimentos de Adleman, se han realizado numerosos avances, y se ha probado que se pueden construir varias Máquinas de Turing2​.3​

Esta es una tecnología todavía en etapas bastante tempranas, por lo cual su uso existe más que nada como una opción teórica. Todavía usar computación convencional es una opción más eficiente que usar este método.

Ejemplo de Aplicación

Se muestran a continuación los pasos seguidos por Adleman para resolver el problema del camino Hamiltoniano.

Se tiene un grafo direccionado G con n vértices vi. Existen aristas conectando algunos vértices. Se denota la arista que conecta al vértice vi con vj como ei→j.

Para simplificar el ejemplo, y sin pérdida de generalidad, se considera que se comienza en el vértice v1 y se termina en el vértice vn

Los pasos son:

1. Generar caminos aleatorios.
2. Seleccionar aquellos que comiencen con v1 y terminen con vn.
3. Seleccionar sólo aquellos caminos que cuenten con exactamente n vértices.
4. Seleccionar sólo aquellos caminos que tengan cada vértice una sola vez.
5. Si queda algún camino en la muestra, responder SI, de otra forma responder NO