Hoja 1
Capítulo 9 : Introducción a los lenguajes formales
  Introducción
    -Un lenguaje es un conjunto de símbolos y métodos para estructurar y combinar dichos símbolos
-también recibe el nombre del idioma y como tal consta de todos los símbolos válidos por dicho lenguaje y los métodos para estructurar correctamente cada una de las palabras, frases y oraciones
  Gramáticas y lenguajes formales
    -Lenguaje L (G). Este tipo de lenguaje se basa en la gramática, así como en las reglas o métodos para la creación de palabras propias del lenguaje
-Un lenguaje L consiste en una gramática con todos los arreglos que se pueden obtener a partir del estado inicial y las composiciones
  Estructuración de las gramáticas
    -Las gramáticas están integradas por varios elementos que permiten la estructuración de palabras
-La gramática es el sistema que permite establecer las reglas que han de aplicarse a un lenguaje
  Clasificación de las gramáticas
    -Tipo 0: Si no se pone ninguna restricción a las composiciones de G
-Tipo 1: Si para cualquier composición d1->d2 de la gramática G, la longitud de símbolos de la izquierda de la composición (d1) es menor o igual a la longitud de símbolos de la derecha (d2).
Típo 2: Si el laldo izquierdo de cada composición es un símbolo no terminal y el lado derecho consta de uno o más símbolos terminales y/o no terminales.
-Tipo 3: Si el lado izquierdo de la composición es un símbolo no terminal y el lado derecho tiene uno o más símbolos, incluyendo a lo más un símbolo no terminal.
  Gramáticas regulares
    -Se representan principalmente por medio de autómatas finitos los cuales son elementos generadores de palabras de un lenguaje, en donde una palabra se genera comenzando en el símbolo inicial y terminando como una cadena de símbolos terminales que no contiene ningún símbolo no terminal
  Gramáticas libres de contexto
    -Este tipo de gramáticas son las más usadas en la elaboración de compiladores, traductores e intérpretes, y se pueden representar por medio de árboles de derivación, representación BNF y diagramas sintácticos
  Representación mediante árboles de derivación
    -El procedimiento para determinar si una palabra pertenece a un lenguaje por el método de árboles de derivación es semejante al desarrollado por medio de composiciones
-se estructura un árbol teniendo como raíz de ese árbol al símbolo inicial s y colocando como hijos a los signos del lado derecho de la composición
  Representación BNF (Backus-Naur)
    -se utiliza con frecuencia para la representación de lenguajes formales como C, Pascal, Basic, etc.
  Diagramas sintácticos
    -Esta es una forma gráfica para representar una gramática por medio de gráficas dinámicas que permiten determinar en forma más ilustrativa si una palabra pertenece a un lenguaje; a esta gráfica se le conoce como diagrama sintáctico o diagrama de sintaxis
  Autómatas finitos
    -Todo proceso que recibe una o varias entradas, que transforma estas entradas y después emite una salida recibe el nombre de sistema
-Los autómatas finitos también reciben como entrada información que procesan y en función de ello emiten una salido
-Un autómata finito recibe una palabra, la cual debe procesar por medio de un recorrido a través de los diferentes estados que integran el autómata
  Terminología básica
    -Las gramáticas regulares son parte esencial de los lenguajes regulares
-Los autómatas finitos son una representación gráfica de los lenguajes regulares
-Una palabra que pertenece a un lenguaje realmente es una cadena de símbolos o caracteres y por eso la relación que existe entre símbolos, cadenas, lenguajes, alfabetos y gramáticas es importante
  Lenguajes regulares
    -Con el alfabeto ∑ es posible formar una gran cantidad de lenguajes, pero no existe un método efectivo para saber cuántos de ellos son regulares
-Todos los lenguajes sobre ∑ son sublenguajes del lenguaje universo ∑*, en lugar de ellos se utilizarán algunas propiedades de los lenguajes para determinar cuales de ellos son regulares
  Expresiones regulares
    -Es una nueva forma de expresar los lenguajes regulares y tiene como finalidad facilitar la manipulación y simplificación de los mismos
  Diagrama de transición
    -los estados se representan por medio de un círculo con el nombre del estado dentro de ella
-Los estados de aceptación o finales se distinguen porque tienen doble círculo, las transiciones se representan por aristas y se etiquetan con un símbolo del alfabeto
-El estado inicial se distingue porque se hace incidir sobre él una flecha
  Autómatas finitos determinísticos
    -es determinístico si por medio de la función de transición es posible determinar claramente cuál es el estado siguiente
-El autómata anteriormente visto es un AFD ya que cuando se está en un estado cualquiera y se tiene un símbolo del alfabeto es posible determinar claramente cuál es el estado siguiente
  Autómatas finitos no determinísticos
    -La función de estado siguiente, no conduce a un estado único determinado
  Máquinas de estado finito
    -Es una forma de representar los autómatas finitos
-no existen estados aceptados y donde los símbolos de salida se colocan juntamente con los símbolos de entrada en cada una de las aristas de la máquina
  Máquinas de Turing
    -Una máquina de Turing consiste en una cinta que se extiende de manera infinita, en donde se escribe o se lee información por medio de una cabeza de lectura-escritura
  Teoría de la computabilidad
    -Es la parte de la computación que analiza y determina los problemas que pueden resolverse por medio de un algoritmo o bien por alguna de las MT
  Teoría de la complejidad
    -La complejidad es la cantidad de recursos necesarios para resolver un problema como son tiempo y espacio
-El tiempo es el número de pasos de ejecución de un algoritmo para resolver un problema y el espacio la cantidad de memoria utilizada para resolver dicho problema
  Aplicación de los lenguajes formales
    -Las máquinas de estado finito y los AFD admiten lenguajes regulares, lenguajes simples que normalmente se observan funcionando en circuitos lógicos de control sencillos, en donde las operaciones a realizar, están completamente determinadas por la información de entrada