Lenguajes → todo lenguaje naturao/artificial esta definido sobre un alfabeto y poseen un grupo de reglas sintácticas y semánticas.

Clasificación de los lenguajes según Chomsky

→lenguajes regulares : representan regularidades /repeticiones y simples LR

→lenguajes libres de contexto: abarcan los lenguajes de programación permiten remplazar símbolos sin tener en cuenta contexto LLC

→lenguajes sensibles de contexto: cada símbolo se reemplaza según el contexto LSC

→ lenguajes recursivamente enumerables:lenguaje pocos restrictivos 

MAQUINA DE ESTADO: sistema abstracto q permite modelizar un sistema discreto de la vida real 

–Reconocedoras: detectan patrones pero no proveen una salida

–Traductoras: Recibe entrada y genera salida 

Autómatas

Son las maquina de estado mas sencilla, y están compuestas por: 

NODOS

SON ESTADOS EVENTOS/TRANSICIONES:
Situaciones instantáneas que marcan un cambio a otro (las flechas)

TIPOS DE ESTADOS

Hay 1 estado inicial uno o mas estados finaes y 0 o mas estados intermedios, todos los estados son excluyentes e/si TRAYECTORIA:
Es el camino recorrido desde el estado incial hasta el final

Estos atutomatas tienen una función reconocedora y sirven para validar cadenas de acciones.

AFD Definición FORMAL (quintupla)

K: conjunto de todos los estados posibles

S: estado inicial

F: conjunto de estados finales

Σ: alfabeto sobre el que se construye el lenguaje L

δ:Función transición que a partir de un estado y símbolo del alfabeto se llega a un nuevo y único estado

Equivalencia y minimización

Método mecanino para simplificar un afd llegando a la expresión mas simple del mismo.

Compatibles:

dos estados q y q’ son compatibles si ambos son estados finales o ambos son no finales

Equivalentes:

dos autómatas finitos m y m’ son equivalentes si aceptan las mismas palabras, es decir el mismo lenguaje

TEOREMA DE MOORE

es un algoritmo de comparación que permite establecer si dos autómatas finitos son equivalentes o no, para ello se contruye un árbol de comparación

pasos: 1.Eliminar estados inaccesibles

2-Par ordenado «raíz»(estados inciales de cada autómata

3-Realizar todas las transiciones posibles d c/par de estados compatibles

Si los estados son incompatibles No son equivalentes

AFN NO DETERMINISTICO

pueden faltar flechas, salir varias fldchas de la misma etuiqueta, salir una flecha etiquetada con una palabra, misma <= pero con palabra vacía épsilon

Def formal igual que el afd, pero δ cambia por Δ que deja de ser una función y se convierte en una relación

Conversión de afn a un afd

1-construir tabla con tantas columnas como ismbolos tnega el alfabeto

2-en la 1era fila escribir el nodo incial y en c/columna escribir los estados a los que se llega por medio de la entrada que encabeza la columna

3-copiar como encabezado de la fila nueva o siguiente cada nuevo conjunto de estados obtenidos anteriormente. No repetir los estados obtenidos anteriormente en la columna L

4-Repetir paso 3 hasta llenar la tabla

5-Reescribir el autómata, marcando el S y los Estados finales

6-En caso de una transición vacía agrego un nodo ficticio y agreog las transiciones debidas. Luego se construye un grafo

Autómata finito de pila

al autómata fininto, le agregamos un almacenamiento llamado pila. En dicha pila, se pueden ir depositando carácter a carácter cadenas confomando la pila

El estado de la pila tiene que estar vacío (z)

Se puede apilar, desapilar elementos iguales o distintos. 

DEF FORMAL (Séxtuplo)        Para las transiciones usamos

K                                            w:secuencia de caracters que se                                                        consumen

Σ: alfabeto de entrada——alfa:es lo que se saca de la pila

δ:alfabeto de pila ————Beta:es lo que se pone en la pila

S: estado inicial —————todo esto lo diferencia de un AF

F: conjunto de estados finales

Δ: relación de transición

Cuando la palabra de entrada es aceptada en afp?

1 La palabra de entrada se debe haber consumido

2 El AFP se debe encontrar en un estado final

3 La pila debe estar vacía

Definición formal de gramática (cuádrupla)

RP: Regla de producción

T: Conjunto de símbolos terminales (Caracteres del alfabeto)

NT: Conjunto de símbolos no terminales (variables)

S: Símbolo incial a partir del cual se derivan todas las palabras validas

Ambigüedad                            G es la cuádrupla

Cuando hay mas de un árbol de derivación para una misma gramática se dice que es ambigua, para evitarlo debemos agregar nuevos terminales que eliminen la ambigüedad

°Si la gramática genera mas palabras entonces G es incompleta

°Si hay mas de un árbol de derivación para una palabra, entonces G es ambigua—————————Completa=>

°Todas las cadenas en el lenguaje tienen una única derivación

Árbol de derivación

°
Estructura que muestra como se puede generar una cadena de símbolos a partir del símbolo inicial de una gramática

°Cada nodo del árbol representa un símbolo ne la derivación y las ramas del árbol muestran la reglas de producción que se aplican para derivar los símbolos

°Sirven para determinar si  una gramática es ambigua o no

Clasificación de gramáticas

tipo: 0 Gramática recursivamente enumerables (GRF)

tipo: 1 Gramáticas sensibles al contexto (gsc)

tipo: 2 Gramática libre de contexto (glc)

tipo: 3 Gramáticas regulares (gr)

Relación con AF

Su capacidad para describir y reconocer los mismos conjuntos de lenguaje

Gramática regular y características

Estas son las mas restringidas por que presentan regularidades o repeticiones en la conformación de sus palabras

°Características

°El lado derecho de la RP debe contener un símbolo temrinal y a lo sumo un símbolo no terminal

°Lineal a derecha:A->aB o A->a ‘B aparce a derecha de a’

°Lineal a izquierda:A->Ba o A->a 

Terminales:Elemento del alfabeto (minúscula)

No terminales:Elementos nuevos variables (mayúscula)

Si contiene una mayúscula ya es no terminal

Gramáticas libres de contexto

Los glc, se caracteriza por presentar un símbolo no terminal del lado izq de una regla de producción y una combinación de dos o mas símbolos terminales y/o no terminales del lado derecho.

Maquina de turing

Maquina abstracta mas poderosa concoida, cuenta con una cabeza lectora que también es de escritura, también cuenta con una cinta bidireccional.

Que pasa cuando se llega al estado halt?

La Palabra se acepta solo si llega a halt en algún momento finalizando el proceso de lectura y no mira que hay luego

Que significa que la maquina de turing escriba en la cinta -> que no acepta la palabra

  Si el carácter leído es una letra b, escribe en la cinta una b, no

avanza ni retrocede. No sigue procesando, por lo cual NO

valida la palabra

Operación de MI

1-lee un carácter en la cinta. 2-efectúa una transición de estado. 3-realiza una acción en la cinta (escribe símbolo o mueve la cabeza de izq o derech)

Definición formal (quíntuplo)

K: conjunto de todos los estados tal que h(halt) e K,

S e K: estado inicial

r: es el alfabeto de la cinta, donde esta incluido el espacio en blanco y todos los caracteres de Σ 

Σ: alfabeto de entrada, donde no incluye el espacio en blanco

δ:Función transición que a partir de un estado y a travez de la lectura de un carácter de la cinta, pasa a un estado nuevo, pudiendo escribir en la cinta, moverse a derecha o a izq

Relación CON AF

Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida .

Etiquetas: Autómatas Finitos, Gramáticas, Lenguajes Formales, Máquina de Turing, Máquinas de Estado, Teoría de Autómatas