Autómatas y Lenguajes Formales

DEFINICION Y FUNCIONAMIENTO
1. ¿COMO FUNCIONA? El autómata comienza en el estado inicial con un conjunto de símbolos; su paso de un estado a otro se efectúa a través de la función de transición, la cual, partiendo del estado actual y un conjunto de símbolos de entrada, lo lleva al nuevo estado correspondiente.
2. ¿QUE ES? Modelo computacional consistente en un conjunto de estados bien definidos, un estado inicial, un alfabeto de entrada y una función de transición. Este concepto es equivalente a otros como autómata finito o máquina de estados finitos.
ANTECEDENTES Y ACTUALIDAD
1. En el siglo XVII, cuando en Europa existía gran pasión por la técnica, se perfeccionaron las cajas de música compuestas por cilindros con púas, que fueron inspiradas por los pájaros autómatas que había en Bizancio y que podían cantar y silbar.
2. A principios del siglo XVIII, el ebanista Roentgen y Kintzling mostraron a Luis XVI un autómata con figura humana llamado "La tañedora de salterio".
3. Los inventores más célebres son Pierre Jacquet Droz, autor de "El dibujante" y "Los músicos", y M. de Vaucanson, autor de "El pato digeridor", un personaje que aleteaba, parloteaba, tragaba grano y evacuaba los residuos.
4. El autómata más conocido en el mundo es el denominado “Máquina de Turing”, elaborado por el matemático inglés Alan Turing.
5. Actualmente se puede decir que un termostato es un autómata, puesto que regula la potencia de calefacción de un aparato (salida) en función de la temperatura ambiente (dato de entrada), pasando de un estado térmico a otro.
LENGUAJE
1. ALFABETO
  1. Conjunto de todos los símbolos válidos o posibles para una aplicación. Por tanto, en el campo de los autómatas, un alfabeto está formado por todos los caracteres que utiliza para definir sus entradas, salidas y estados.
2. FRASE
  1. Una frase es la asociación de un conjunto de símbolos definidos en un alfabeto (cadena) que tiene la propiedad de tener sentido, significado y lógica.
    1. Las frases parten del establecimiento de un vocabulario que define las palabras válidas del lenguaje sobre la base del alfabeto definido. Una frase válida es aquella que cumple con las reglas que define la gramática establecida.
3. CADENA VACIA
  1. Se dice que una cadena es vacía cuando la longitud del conjunto de caracteres que utiliza es igual a cero, es decir, es una cadena que no tiene caracteres asociados.
    1. Este tipo de cadenas no siempre implican el no cambio de estado en un autómata, ya que en la función de transición puede existir una definición de cambio de estado asociada a la entrada de una cadena vacía.
4. LENGUAJE
  1. Se puede definir un lenguaje como un conjunto de cadenas que obedecen a un alfabeto fijado.
    1. Un lenguaje, entendido como un conjunto de entradas, puede o no ser resuelto por un algoritmo.
  2. FORMAL
    1. Un lenguaje formal está constituido por un alfabeto, un vocabulario y un conjunto de reglas de producción definidas por gramáticas. 22 Las frases válidas de un lenguaje formal son aquellas que se crean con los símbolos y palabras definidas tanto en el alfabeto como en el vocabulario del lenguaje y que cumplen con las reglas de producción definidas en las gramáticas.
GRAMATICA
1. GRAMATICAS FFORMALES
  1. Una gramática es una colección estructurada de palabras y frases ligadas por reglas que definen el conjunto de cadenas de caracteres que representan los comandos completos que pueden ser reconocidos por un motor de discurso.
    1. La función de una gramática es definir y enumerar las palabras y frases válidas de un lenguaje. La forma general definida por BNF es denominada regla de producción y se puede representar como::
      1. <regla> = sentencias y frases. *
    2. Un ejemplo de una gramática que define las opciones de un menú asociado a una aplicación de ventanas puede ser::
      1. <raiz> = ARCHIVO | EDICION | OPCIONES | AYUDA.
2. JERARQUERIZACIÓN DE LAS GRAMÁTICAS
  1. Las gramáticas pueden ser de distintos tipos, de acuerdo con las características que rigen la formulación de reglas de producción válidas, todos los cuales parten de las gramáticas arbitrarias que son aquellas que consideran la existencia infinita de cadenas formadas por los símbolos del lenguaje.
  2. GRAMÁTICAS SENSIBLES AL CONTEXTO
    1. Este tipo de gramáticas tiene la característica de que el lado derecho de la regla de producción siempre debe ser igual o mayor que el lado izquierdo.
  3. GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO
    1. Una gramática independiente del contexto es aquella que cumple con las propiedades de la gramática sensible al contexto y que, además, tiene la característica de que el lado izquierdo de la regla de producción sólo debe tener un elemento y éste no puede ser un elemento terminal.
  4. GRA,ÁTICAS REGULARES
    1. Una gramática es regular cuando cumple con las características de la gramática independiente del contexto y, además, se restringe a través de las reglas de producción para generar sólo reglas de los dos tipos anteriores.
PROPIEDADES DE INDECIBILIDAD
1. Se dice que un lenguaje es indecidible si sus miembros no pueden ser identificados por un algoritmo que restrinja todas las entradas en un número de pasos finito. Otra de sus propiedades es que no puede ser reconocido como una entrada válida en una máquina de Turing. Asociados a este tipo de lenguaje existen, de la misma manera, problemas indecidibles que son aquellos que no pueden ser resueltos, con todas sus variantes, por un algoritmo. En contraposición con el lenguaje indecidible y los problemas asociados a este tipo de lenguajes existen los problemas decidibles, que están relacionados con lenguajes del mismo tipo y que tienen las características opuestas. Este tipo de lenguajes se conoce, también, como lenguajes recursivos o lenguajes totalmente decidibles.

Next up

Autómatas y Lenguajes Formales

Description

Resource summary

Similar

	Created by Alonso Sepulveda over 3 years ago