1. ¿Qué es un autómata?
1.1 En electrónica un autómata es un sistema secuencial, aunque en ocasiones la palabra es utilizada también para referirse a un robot. Puede definirse como un equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales. Sin embargo, la rápida evolución de los autómatas hace que esta definición no esté cerrada. Obtenido de: https://www.ecured.cu/Aut%C3%B3mata
1.2 Los autómatas vienen a ser mecanismos formales que "realizan" derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generada en una gramática si y sólo si la palabra hace transitar al autómata correspondiente a sus condiciones terminales. Por esto es que los autómatas son analizadores léxicos (llamados en inglés "parsers") de las gramáticas a que corresponden. Obtenido de: http://automatas-conceptos.blogspot.com/
1.3 Instrumento o aparato que encierra dentro de sí el mecanismo que le imprime determinados movimientos. También, la entidad abstracta que se obtiene al prescindir de la naturaleza física y disposición espacial de sus partes, quedando un conjunto de estados no especificados físicamente, entradas de datos o impulsos y salidas de resultados o acciones vinculados por determinadas reglas. Obtenidos de: https://es.thefreedictionary.com/aut%C3%B3mata
2. Qué es una máquina?
2.1 Una máquina es una herramienta que contiene una o más partes que utiliza la energía para llevar a cabo una acción destinada. Las máquinas están normalmente alimentadas por medios mecánicos, químicos, térmicos o eléctricos, y con frecuencia están motorizadas. Históricamente, una herramienta eléctrica también requiere partes móviles para clasificar como una máquina. Sin embargo, el advenimiento de la electrónica ha llevado al desarrollo de herramientas eléctricas sin partes que se consideren elementos en movimiento. Obtenido de: https://es.wikipedia.org/wiki/M%C3%A1quina_(tecnolog%C3%ADa)
2.2 La palabra máquina es una palabra que presenta un uso recurrente en nuestro idioma dado que denomina al aparato, artefacto, compuesto por un conjunto de mecanismos y de piezas, tanto fijas como móviles, cuya marcha permite dirigir, regular, o en su defecto, cambiar la energía para llevar a cabo un trabajo con una determinada misión. Obtenido de: https://www.definicionabc.com/general/maquina.php
2.3 Objeto fabricado y compuesto por un conjunto de piezas ajustadas entre sí que se usa para facilitar o realizar un trabajo determinado, generalmente transformando una forma de energía en movimiento o trabajo. Obtenido de: https://www.lexico.com/es/definicion/maquina
3. ¿Qué es un lenguaje?
Un conjunto de cadenas, todas ellas seleccionadas de un ∑*, donde ∑ es un determinado alfabeto se denomina lenguaje. Ya que estas pueden ser cualquier cadena que cumpla con lo siguiente, está formada por los símbolos. Los lenguajes habituales pueden interpretarse como conjuntos de cadenas.
Tipos de Lenguajes:
- LENGUAJES DECLARATIVOS: Es fundamentalmente lenguajes de órdenes, dominados por Sentencias que expresan “lo que hay que hacer” en vez de “cómo hacerlo”.
- LENGUAJES DE ALTO NIVEL: Son los más utilizados como lenguajes de programación permiten que los algoritmos se expresen en un nivel y estilo de escritura fácilmente legible y comprensible por otros programadores.
- LENGUAJE ENSAMBLADOR: Es el programa en que se realiza la tracción de un programa escrito en un programa escrito en ensamblador y lo pasa a lenguaje máquina. Directa o no directa de la traducción en que las instrucciones no son más que instrucciones que ejecuta la computadora.
- LENGUAJE MAQUINA: Es como la maquina interpreta lo que nosotros queremos hacer es una lectura de 0 y 1 es decir binario.
4. ¿Cómo está constituido un lenguaje?
- Fonología.
Es el primero de los componentes del lenguaje e involucra las reglas de estructura y secuencia de los sonidos de nuestro idioma. El desarrollo fonológico ocurre en períodos que van desde el nacimiento hasta el primer año de vida, que es cuando el niño empieza a balbucear o hacer sonidos semejantes al idioma. A partir del primero y hasta los dos años de edad el niño comienza a pronunciar algunas palabras, un desarrollo que se extiende hasta aproximadamente los seis años de edad.
- Semántica.
La semántica no es otra cosa que el vocabulario y los conceptos que este representa por medio de palabras. Al igual que el desarrollo fonológico, el desarrollo semántico ocurre en etapas. A partir del primer año de vida los niños comienzan a comprender que el lenguaje es un medio de comunicación. A partir del segundo año de vida el vocabulario del bebé comienza a crecer exponencialmente. A partir de los tres a cinco años de edad los niños utilizan vocabulario pero muchas veces de manera incorrecta. Por ejemplo un niño dirá “pato” en lugar de zapato. Del sexto año en adelante la mayoría de niños puede comprender el significado de las palabras y saben las definiciones de múltiples vocabularios, incluso pueden establecer las diferencias de aquellos que suenan parecidos como ojo y rojo.
- Gramática.
Este es el tercer componente de todo idioma e involucra dos partes, la primera la sintaxis, que son las reglas por medio de las cuales se forman las oraciones. El segundo componente de la gramática es la morfología. La morfología se ocupa del uso de marcadores gramaticales que indican tiempo, voz pasiva o activa entre otros. A partir de los dos años de edad la mayoría de niños puede formar oraciones simples pero a partir de los seis son capaces de utilizar estructuras gramaticales complejas.
- Pragmática.
Este es el cuarto y último componente de cualquier idioma, por pragmático o pragmática entendemos las reglas para el uso apropiado y efectivo de la comunicación, la pragmática involucra tres habilidades:
- Primero: utilizar correctamente el lenguaje para saludar o solicitar algo.
- Segundo: alternar el uso del lenguaje de manera que le hablemos diferente a cada persona dependiendo quién es él o ella.
- Tercero: seguir reglas tales como esperar a que la otra persona deje de hablar para comenzar nosotros y mantenerse en el tópico de la discusión.
A partir de las edades de uno o dos años, los niños pueden involucrarse en conversaciones en donde toman turnos para hablar. A la edad de tres, los niños pueden comprender la intención del mensaje recibido. Por ejemplo, una madre puede preguntar ¿quieres leche? Y el niño entiende que ahora puede hablar para contestar a la pregunta. A la edad de seis y más adelante el niño es capaz de sostener conversaciones más complejas como por ejemplo hablar por teléfono.
5. Relación entre lenguaje y gramática
El lenguaje determina la gramática que usará el autómata y a su vez, la gramática son las reglas del idioma.
6. Relación entre lenguaje y autómata
Formalmente, dado un autómata finito no determinista:
M = (E, A, T, e0, F) el lenguaje aceptado por M es L(M) definido como
L(M)= {w | existe una computación aceptadora de M con entrada de w}
para el cual se cumplen los siguientes teoremas:
Dado un autómata finito no determinista (AFnD) M, existe un autómata finito determinista (AFD) M’ tal que L(M) = L(M’).
Construcción de gramáticas a partir de autómatas dados y de forma inversa.
Un lenguaje A es regular si existe un autómata finito determinista M con A = L(M).
Un lenguaje A es irregular si existe un Autómata finito no determinista N con A = L(N).
M = (E, A, T, e0, F) el lenguaje aceptado por M es L(M) definido como
L(M)= {w | existe una computación aceptadora de M con entrada de w}
para el cual se cumplen los siguientes teoremas:
Dado un autómata finito no determinista (AFnD) M, existe un autómata finito determinista (AFD) M’ tal que L(M) = L(M’).
Construcción de gramáticas a partir de autómatas dados y de forma inversa.
Un lenguaje A es regular si existe un autómata finito determinista M con A = L(M).
Un lenguaje A es irregular si existe un Autómata finito no determinista N con A = L(N).
7. ¿A qué se le llama expresión?
Una expresión es la representación o materialización de una idea, mediante el uso de recursos como el habla, la escritura o el lenguaje corporal. Es uno de los principales mecanismos cognitivos que permiten la comunicación entre la mayoría de los seres vivos que habitan la tierra; cada organismo tiene su propio método para informar a otro de su misma especie su estado, aunque sólo se trate de un instinto primitivo de protección o socialización. Igualmente, el término “expresión”, se suele emplear como sinónimo de una palabra o frase con particularidades culturales.
8. Historia y Evolución de los lenguajes
Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene, Post, y Turing.
Estos primeros trabajos han tenido una profunda influencia no solo en el desarrollo teórico de las Ciencias Computacionales., sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.
El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:
1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?
2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación?
3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?
Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que esto no era posible. Las primeras noticias en contra surgen en 1931 con K. Gödel y su Teorema de Incompletitud: “Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo.”
El siguiente paso importante lo constituye la aparición casi simultanea en 1936 de varias caracterizaciones independientes de la noción de calculabilidad efectiva, en los trabajos de Church, Kleene, Turing y Post. Los tres primeros mostraban problemas que eran efectivamente indecidibles; Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible.
Cuando Turing conoció los trabajos de Church-Kleene, demostró que los conceptos de función λ-definible y función calculable por medio de una máquina de Turing coinciden. Naturalmente a la luz de esto la Tesis de Turing resulta ser equivalente a la de Church.
Posteriormente, se demostró la equivalencia entre lo que se podía calcular mediante una máquina de Turing y lo que se podía calcular mediante un sistema formal en general. A la vista de estos resultados, la Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación, y ha servido como punto de partida en la investigación de los problemas que se pueden resolver mediante un algoritmo.
Estos primeros trabajos han tenido una profunda influencia no solo en el desarrollo teórico de las Ciencias Computacionales., sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.
El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:
1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?
2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación?
3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?
Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que esto no era posible. Las primeras noticias en contra surgen en 1931 con K. Gödel y su Teorema de Incompletitud: “Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo.”
El siguiente paso importante lo constituye la aparición casi simultanea en 1936 de varias caracterizaciones independientes de la noción de calculabilidad efectiva, en los trabajos de Church, Kleene, Turing y Post. Los tres primeros mostraban problemas que eran efectivamente indecidibles; Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible.
Cuando Turing conoció los trabajos de Church-Kleene, demostró que los conceptos de función λ-definible y función calculable por medio de una máquina de Turing coinciden. Naturalmente a la luz de esto la Tesis de Turing resulta ser equivalente a la de Church.
Posteriormente, se demostró la equivalencia entre lo que se podía calcular mediante una máquina de Turing y lo que se podía calcular mediante un sistema formal en general. A la vista de estos resultados, la Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación, y ha servido como punto de partida en la investigación de los problemas que se pueden resolver mediante un algoritmo.
No hay comentarios:
Publicar un comentario