Gramáticas Lenguajes Formales Autómatas Finitos

Gramática
1. Lenguaje Humano
  1. Lenguas Naturales
    1. Cuentan con Diversidad
    2. Español Ingles Aleman Frances Chino Árabe etc.
2. Autómata
  1. Dispositivo: -Mecánico -Electrónico -Biológico
    1. Por una Señal cambia de estado
      1. -Reloj electrónico -Máquina lavar -Computadora
  2. Sistema de Estructuración de frases significativas
    1. Lenguajes Formales "artificiales"
      1. Estructurado: Alfabeto Finito y Cadenas logitud finita
        Las Cadenas contienen símbolos de un conjunto
        Alfabeto: {a,b,c} Cadena: {acbbaccacb}
        Puede contener conjunto infinito de palabras
        Genera Palabras (lenguajes)
        Automatas aceptan palabras (lenguajes)
        Conjunto de todas las palabras que pertenecen al lenguaje
        Oraciones con con construcción adecuada
        Clasificación de Lenguajes Formales 1956 Noam Chomsky
        Tipo 0 Gramáticas generales y Máquinas de Turing
        Tipo 1 Gramáticas sensitivo al contexto y Autómatas linealmente acotados
        Tipo 2 Gramáticas libres de contexto y Autómatas finitos con pila
        Tipo 3 Gramáticas Regulares y Autómatas Finitos
        Recursivamente Enumerables-Gramática Regla compresora
        Dependientes de contexto-No reglas compresoras
        Independientes de contexto (mayoría Lenguajes de programación)
        Regulares-Pueden expresar mediante expresiones regulares
        Tipo de lenguaje
        Corresponde una Arquitectura de máquina
      2. Acepta secuencias
        Reglas Sustituir símbolos
        Reglas derivan Frases
        $-AB B-CD D-EF F-GH H-IJ J-KL
        A-motorOn C-luzOn D-EF E-frenoOff F-GH FG-FrenoOn H-IJ I-motorOff J-KL K-luzOFF L-fin
        Sutituir Frase forma Secuencias
        -Encender Motor -Encender luces -Soltar Freno -Poner Freno -Apagar Motor -Apagar Luces
3. Estructuras de gramáticas Conjuntos finitos Símbolos
  1. Conjunto símbolos No terminales Para definir gramática No aparecen en frases
    1. N
      1. <> [ ] ( ) : ; , |
  2. Conjunto símbolos Terminales Símbolos válidos del lenguaje Aparecen en la frases
    1. T
      1. <Oracion> <Sujeto> <Verbo> <adverbio>
  3. Conjunto de Reglas para llevar a cabo sustitución de cadenas. Se llaman Producciones Teniendo parte izquierda y derecha separadas por una flecha. Un par ordenado. o Puede usarse notación de Bakus Nar-Form (BNF)
    1. R
      1. <Oración>::= <sujeto><verbo><adverbio>
        <Oración>::= [Rosa|Oscar] [brinca|trepa] [alto|bajo]
      2. <Oración> -> <sujeto><verbo><adverbio>
        sujeto-->Rosa sujeto-->Oscar Verbo-->brinca Verbo-->trepa Adverbio-->alto Adverbio-->bajo
        Producciones de este ejemplo
    2. El conjunto S consta de símbolos diferentes de N, estos símbolos permiten las producciones
      1. S
        Rosa, Oscar, brinca, trepa, alto, bajo
  4. Una gramática genera un Lenguaje L(G) donde G es gramática
    1. Derivaciones son herramientas para genera lenguaje utilizando la gramática
Autómatas Finitos
1. Remonta a uso de máquinas electromecánicas 1907
  1. Cadena de Andréi Márkov
    1. Ocurrencia de un evento depende de la probabilidad del evento anterior
      1. Autómatas finitos tienen memoria primitiva en que un estado depende del estado anterior
        1943 Máquinas de secuencia Modelo neuronal McCulloch-Pitts
        1950 proliferan máquinas con Lenguajes Regulares y Expresiones Regulares
        1959 Michael O. Rabin y Dana Scott concepto de Autómata finito no determinístico
        1960 Series de potencias y sobre escritura
        1970 Unix Sistema operativo uso masivo de expresiones regulares Inicia uso de autómatas en sistemas dinámicos
2. Autómatas Finitos Determinísticos y no Determinísticos
  1. <E, eo, A, t, F> E=estados posibles eo=Edo. inicia autómata A=alfabeto t=Función de transición-estados F=Estado-final
    1. Determinista
      1. Con cada símbolo de entrada: cambio de un estado a otro
    2. No Determinista
      1. Con símbolo de entrada o cadena vacía Pasa de un estado a otro conjunto de estados no vacío
3. Extensiones de Autómatas
  1. Con Pila
    1. Dispone de una memoria Transición según estado del elemento inicial de la pila. Cambia pila en cada transición
  2. Máquina de Turing
    1. Utiliza secuencia lineal de instrucciones. 1 carácter por instrucción codificadas en tabla. Toma en cuenta estado actual y último dato leído. Dispositivo que puede realizar cualquier operación matemática
  3. Acotado
    1. Máquina acotada linealmente. Memoria en forma de Cinta infinita. Recorre hacia atrás y hacia adelante. Cabezal lee y/o modifica la cinta
4. Máquina de estado finito.
  1. Realizan procesos bien definidos en tiempo discreto. Entrada-Proceso-Salida
    1. Máquina capaz de seguir una secuencia finita de pasos.
      1. Número de pasos=Número de datos
        Entrada diferente-Salida diferente
        Mismos datos entrada-Misma Salida
        Entonces una computación resuelve problema si hay un ALGORITMO
  2. Modelo abstracto para manipulación de símbolos. Genera un conjunto de símbolos como resultado
    1. Por lo que Autómata y Máquina de estados finitos se consideran lo mismo
      1. Por propósitos prácticos el autómata es finito
        El autómata recibe cadena de símbolos y cambia estado por cada símbolo recibido o permanece en ese estado
        Autómata Finito No Determinista
        Un estado inicial. Una única forma de llegar a uno de los estado finales:
        Si posterior a la lectura de símbolos el autómata cambió a uno de los estados finales:
        Entonces es un Autómata Finito Determinista
  3. Por su funcionamiento
    1. Transductoras
      1. Con función de Salida
        Arroja un elemento del conjunto de símbolos de salida
        Máquina de MOORE
        Hexa-tupla
        Q:Conjunto_finito_de_estados Σ:Alfabeto_de_entrada S:Alfabeto_de_salida δ:Función_de_transición__ λ:Función_de_Q_a_S__ q:Estado_inicial q_NOS_ARROJA_UNA_s_DONDE_s_∈_S_ y_q∈Q
        Inicia-Estado_inicial_q Entrega_símbolo_s_al_llegar_a_Estado Función_transición_llega_a_elemento_cadena_entrada_Σ Indica_nuevo_estado_que_adopta (Puede_ser_el_mismo_según_símbolo_leido_y_estado_actual)
        Al llegar a un estado
        Al cambiar de estado (Transición
        Máquina de MEALY
        Hexa-tupla
        Similar a ala de Moore
        DIFERENCIA: λ(qi,a)→s_donde_s_∈_S,_q_∈_Q_y_a_∈_Σ
        Entrega un resultado en cada transición y no al llegar a cada Estado como en la de Moore
        Máquina de TURING
        Q:Conjunto_finito_de_estados_de_la_máquina Σ:Alfabeto_de_entrada_recibe_por_lectura Γ_símbolos_reconocidos_por_máquina_donde_S_∈_Σ_S:Alfabeto_de_salida δ:Función_de_transición_ Recibe_parámetro_ qi=Estado_en_que_se_encuetra_la_máquina_Genera_valor_qk_y_ escribe_?_donde_leyó Se_moverá_izquierda_o_derecha B:_En_Blanco_F:_Conjunto_de_Estados_Finales λ:Función_de_Q_a_S__ q:Estado_inicial q_NOS_ARROJA_UNA_s_DONDE_s_∈_S_ y_q∈Q
        El modelo TURING realiza una COMPUTACIÓN
        Si una máquina imprime dos tipos de símbolos donde son 1 y 0 y el segundo tipo son llamados símbolos de segunda especie: Esa máquina se puede llamar COMPUTADORA
    2. Aceptadoras

Nächster

Gramáticas Lenguajes Formales Autómatas Finitos

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von FM GR vor fast 4 Jahre