Parcial 1 Flashcards
Abstraccion
Acto mental en el que se aisla conceptualmente una propiedad o funcion concreta de un objeto, y se piensa que es, ignorando otras propiedades del objeto en cuestion. Me abstarigo de la implementacion.
Caracteristica reactiva de sistemas concurrentes
Sistema reactivo es aquel que reacciona permanentemente a cambios del ambiente y otros procesos.Suele no requerirse que terminen. Suelen no computar resultados.
Deadlock
Dos o mas procesos (o hilos) esperan mutuamente el avance del otro (o incluso el mismo hilo espera que avance el mismo).
Estados de un proceso
New: Proceso siendo creado.
Running: Proceso se esta ejecutando.
Waiting: Proceso esta esperando que se cumpla algun otro evento.
Ready: Proceso esta pronto para ejecutar, esperando por CPU.
Terminated: Proceso ha terminado.
Exclusión Mutua
Propiedad para controlar concurrencia, requisito de que un hilo en ejecución nunca entre en su sección crítica al mismo tiempo que otro hilo la esta ejecutando.
Interleaving
Intercalacion entre las acciones atomicas que componen un proceso concurrente, es decir entre las acciones atomicas que ejecutan los hilos.
Livelock
Dos o mas procesos no pueden avanzar en su ejecucion porque continuamente responden a los cambios en el estado de otros procesos. Los procesos se ejecutan simultaneamente sin realizar trabajo util, respondiendo a cambios de otros procesos. Esta es la diferencia con un deadlock, porque en este caso los procesos no estan en waiting, mientras que en deadlock los procesos estan en waiting.
Proceso
Unidad de actividad que se caracteriza por la ejecucion de una secuencia de instrucciones, un estado actual y un conjunto de recursos del sistema asociados.
Proceso vs programa
Un proceso es una actividad de cierto tipo que contiene un programa, entradas/salidas y estados.
Es una unidad de actividad que se caracteriza por la ejecución de
una secuencia de instrucciones, un estado actual, y un conjunto
de recursos del sistema asociados
Sistemas críticos
Sistemas cuyas fallas pueden ocasionar daños de gran importancia.
Starvation (inanición)
Uno o mas procesos (o hilos) quedan esperando indefinidamente un mensaje o liberacion de un recurso.
Limitaciones del testing
El testing puede confirmar la presencia de errores pero
nunca garantizar su ausencia.
Control de procesos
Registro especial BCP (bloque de control de proceso) donde el OS agrupa toda la info que necesita conocer respecto a un proceso particular.
Info del control de procesos
Identificador del proceso (Process Identificator -PID-, de sus siglas en Inglés).
•Estado del proceso. Por ej. listo, en espera, bloqueado.
•Contador de Programa: Dirección de la próxima instrucción a ejecutar.
•Valores de registro de CPU. Se utilizan también en el cambio de contexto.
•Espacio de direcciones de memoria.
•Prioridad en caso de utilizarse dicho algoritmo para planificación de CPU.
•Lista de recursos asignados (incluyendo descriptores de archivos y sockets abiertos).
•Estadísticas del proceso.
•Datos del propietario (owner).
•Permisos asignados.
•Signals pendientes de ser servidos. (Almacenados en un mapa de bits)
Hilo
Permiten realizar varias tareas a la vez (concurrentemente). Distintos hilos comparten recursos entre si, como el espacio de memoria, archivos abiertos, etc.
Estos recursos que comparten los hilos son en conjunto conocidos como proceso.
Hilos vs procesos
Procesos son indep, llevan bastante info de estados, e interactuan solo por mecanismos del sistema. Cambiar de un proceso a otro es “costoso” ya que el sistema genera un tiempo desperdiciado para cambiar de proceso. El nucleo o kernel debe intervenir en la comunicacion entre procesos.
Los hilos en cambio comparten sus recursos de forma directa. Como pertenecen a un mismo proceso, cambiar de un hilo a otro es practicamente instantaneo. Son “baratos”. Su comunicacion no requiere invocar al nucleo.
Estados de un hilo
New: Hilo creado pero no inicializado. Le falta el start.
Running: Hilo en ejecución.
Blocked: Hilo blockeado, esperando por algun recurso para continuar.
Waiting: Similar al bloqueo, el hilo espera por la liberacion de un recurso para despertarse.
Terminated: Hilo terminó su ejecución.
Que tiene un hilo
- Estado.
- Contexto del procesador.
* Punto en el que estamos ejecutando, la instrucción.
* Se usa para reanudar un hilo que fue interrumpido con, para poder continuar la ejecución del hilo. - Pila de ejecución, donde se irá metiendo y sacando instrucciones. (Lugar donde almacenaremos las instrucciones que van a ser ejecutadas).
- Espacio de almacenamiento estático donde almacenará las variables.
- Acceso a los recursos de la tarea,
Multiprogramación, Multiprocesamiento y procesamiento distribuido
Multiprogramacion:Gestion de varios procesos dentro de un sistema mono-procesador. No se logra procesamiento en paralelo y se produce sobrecarga en el intercambio de procesos, pero se eficientiza el utso del procesador en general.
Multiprocesamiento: Gestión de varios procesos dentro de un sistema multi-procesador.
Procesamiento distribuido: Gestion de varios procesos, ejecutandose en sistemas de computadores multiples y distribuidos.
Donde se puede presentar concurrencia?
Multiples aplicaciones
Apicaciones estructuradas: conjunto de hilos concurrentes
Estructura del sistema operativo: conjunto de procesos e hilos manejan el SO.
Tipos de interaccion entre procesos
Tres casos:
procesos no tienen conocimiento de los demas
procesos tienen conocimiento indirecto de los demas
procesos tienen conocimiento directo de los demas
Competencia entre procesos por los recursos
Los procesos concurrentes entran en conflicto cuando
compiten por el uso del mismo recurso.
La ejecución de un proceso puede influir en el comportamiento
de los procesos que compiten.
Al haber procesos en competencia, surge la necesidad de la exclusion mutua, es decir que solo un procesos pueda acceder a una seccion critica en un momento dado.
Sin embargo, hacer cumplir la exclusion mutua puede llevar a interbloqueos.
Seccion critica
Parte de un programa que accede a un recurso critico, es decir un recurso no compartible, por lo que si se accediera en simultáneo por más de un hilo llevaría a problemas de concurrencia y por lo tanto fallas en la ejecucion.
Requisitos para exclusión mutua
Solo un hilo tiene permiso para entrar a seccion critica por vez.
Hilo (proceso) no puede solicitar acceso a seccion critica para luego demorarse indefinidamente.
No se debe suponer sobre velocidad relativa de los procesos o numero de procesadores.
Posibilidades al ejecutar primitiva SEND de un proceso
Proceso emisor se bloquea hasta que recibe el mensaje o no se bloquea.
Posibilidades al ejecutar primitiva RECEIVE en un proceso
Si previamente se envio un mensaje, este se recibe y continua la ejecucion.
Si esto no sucede, entonces el proceso se bloquea hasta que llegue un mensaje o continua, abandonando intento de recepcion.
Tipos de combinaciones de procesos
1) Envio y recepcion bloqueantes
2) Envio no bloqueante, recepcion bloqueante
3) Envio no bloqueante, recepcion no bloqueante
Programacion paralela
Muchas instrucciones se ejecutan en simultaneo. Para problemas grandes, a menudo se pueden dividir en varios mas pequeños, que se resuelven en simultaneo.
Programacion concurrente
Composicion de computos que avanza colaborativamente para garantizar un resultado u operacion. Se deben coordinar las secuencias de las interacciones o comunicaciones entre diferentes computos, como asi tambien el acceso a los recursos que se comparten.
Operacion atomica
Aquellas que siempre se ejecutan hasta terminar por completo. No pueden estas parcialmente completas
Condicion de carrera
Cuando el resultado de la ejecucion de varios hilos concurrentes puede ser correcto o incorrecto dependiendo de como se entrelacen. Basicamente se cuando varios hilos leen, modifican y escriben una misma variable, probablemente la corrompan.
Metodos y sentencias Synchronized
Todos los objetos tienen un lock asociado, que se puede adquirir o liberar con esta primitiva.
Se puede poner en el metodo (exclusion mutua), en este caso si se esta ejecutando el metodo sync, no se podra ejecutar ningun otro metodo sync del mismo objeto o clase (en caso metodo sync estatico).
O puede ponerse en bloque de codigo (seccion critica).
Si un thread ejecuta synchronized y el lock esta tomado, se suspende hasta que este se libera y puede continuar.
Comunicacion entre hilos
Hay metodos que permiten esto, que si o si deben ejecutarse dentro de un bloque synchronized:
wait(): le dile al hilo de llamada que abandone el bloqueo y se vaya a dormir hasta que algun otro hilo ejecute notify().
notify(): Despierta a un hilo que invoco wait() en el mismo objeto. Cabe aclarar que notify() no abandona el lock, solo despierta al otro hilo.
notifyAll(): despierta a todos los hilos que llamaron a wait().
Semaforo
Este objeto tiene un contador que protege el acceso a uno o mas recursos compartidos, no necesariamente en el mismo bloque. Tiene una lista/cola de procesos, en la que se incluyen los procesos suspendidos a la espera de su cambio de estado.
Pueden ser binarios, es decir solo toman valores 0 y 1, o no binarios, que pueden tomar cualquier valor Natural.
Semaforo=0 lock cerrado
Semaforo >0 lock abierto
Metodos basicos:
acquire() y release()
Si esta en 0 y aparece un acquire(), manda a ese hilo a dormir hasta que el semaforo sea mayor a 0.
A diferencia del lock, el semaforno no tiene owner (dueño), el contador va controlando si el semaforo permite pasar a un hilo o no.
Reentrant lock
Esta clase provee bloqueo de exclusion mutua con el mismo comportamiento que synchronized, solo un hilo por vez puede tener el bloqueo en un momento dado.
Es importante envolver el bloque de codigo en try catch finally para asegurar que se libera el lock.
Metodos basicos:
lock(), unlock(), isLocked(), tryLock(), isLocked(), entre otros.
ReadWriteLock
Es una interface, que me permite manejar dos bloqueos, uno de lectura y otro de escritura.
Es importante envolver el codigo en try-catch-notify para asegurar que se libere el lock.
La idea es que generalmente es seguro leer variables en simultaneo, siempre y cuando no se las modifique.
El bloqueo de lectura puede ser mantenido por varios hilos a la vez, pero cuando uno tiene el de escritura todos los demas esperan.
CountDownLatch
Es una clase. Lo que hace es que uno o mas hilos esperen hasta que se realicen determinadas operaciones. Se inicializa con un valor entero que representa el numero de acciones a esperar.
Metodos basicos:
await(): hilo que lo ejecuta espera.
countDown(): hilo lo ejecuta al terminar una acción y decrementar el contador.
Cuando el contador llega a 0, la clase despierta a todos los hilos que ejecutaron await().
CyclicBarrier
Es una clase. Se utiliza para sincronizar dos o mas hilos en un punto determinado, similar a CountDownLach, pero mas poderosa.
Se inicia con el numero de hilos que se sincronizaran en un punto determinado.
Cuando un hilo llegas a ese punto, llama al metodo await() para esperar a los demas. Cuando el ultimo hilo llama a await(), la clase despierta a todos los hilos y continuan su trabajo.
La ventaja es que le podemos pasar un Objeto ejecutable como parametro al inicializarla, entonces ejecutara este objeto como un hilo cuando todos los hilos hayan llegado al punto en comun.
Sistemas reactivos
Sistemas informaticos que responden continuamente a su entorno a una velocidad determinada por este. Realizan procesos no terminados basados en estados que estan interactuando con el entorno para habilitar, aplicar o prevenir cierto comportamiento en el mismo. A menudo realizan procesos en paralelo. Se diferencian de los sistemas transformacionales, que no interactuan con el ambiente ni responden a estimulos.
Arquitectura dirigida por eventos (EDA)
Es un patron de arquitectura de software impulsado por la produccion, deteccion, consumo y reaccion a eventos. Un sistema dirigido por eventos posee emisores y consumidores de eventos.
Sistemas EDA estan diseñados para entornos no predecibles y asincronos.
Símbolo
Es una entidad abstracta, que no se va a definir, pues se toma como axioma. Puede ser una letra, numero, caracter, etc.
Vocabulario o alfabeto
Es un conjunto finito de simbolos, no vacio. Se define por enumeracion de los simbolos que contienen.
Cadena
Es una secuencia finita de simbolos de un determinado alfabeto.
Longitud de una cadena: numero de simbolos que contiene.
Existe la cadena vacia, se denota con lambda.
Se pueden concatenar cadenas, obviamente.
Universo del discurso
El conjunto de todas las cadenas que se pueden formar con los simbolos de un alfabeto V se denomina universo del discurso de V y se representa W(V). Evidentemente este conjunto es infinito.
Clausura positiva de un alfabeto: esta formada por el universo del discurso del alfabeto sin contar la cadena vacia.
Clausura o cierre de un alfabeto: esta formada por el universo del discurso del alfabeto, incluyendo la cadena vacia.
Lenguaje
Se denomina lenguaje sobre el alfabeto V a un subconjunto del universo del discurso.
Tambien se puede definir como un conjunto de cadenas de un determinado alfabeto.
Los lenguajes se definen por las propiedades que cumplen las cadenas contenidas en estos.
El lenguaje vacio existe y se denota con una fi.
Gramática
Es un ente formal para especificar, de manera finita, el conjunto de cadenas de simbolos que constituyen un lenguaje.
Es una cuadrupla G=(VN,VT,P,S) donde:
VN=conjunto finito de simbolos no terminales (estados).
VT=conjunto finito de simbolos terminales (eventos).
P=conjunto de producciones o reglas de derivacion.
S=simbolo inicial y pertenece a VN.
Todas las cadenas del lenguaje definido por la gramatica estan formados con simbolos del VT.
El VN es el conjunto de simbolos introducidos como elementos auxiliares para la definicion de la gramatica, y que no figuran en las cadenas del lenguaje.
El simbolo inicial S es un simbolo no terminal a partir del cual se aplican las reglas de derivacion de la gramatica para obtener las distintas cadenas del lenguaje.
La producciones P son las reglas que se aplican desde S para obtener las cadenas del lenguaje.
Autómata
Es una construccion logica que recibe una entrada y produce una salida en funcion de todo lo recibido hasta ese instante.
Es una quintupla A=(E,S,Q,f,g) donde:
E=conjunto de entradas o vocabulario de entrada.
S=conjunto de salidas o vocabulario de salida.
Q=conjunto de estados.
f: ExQ –> Q es la funcion de transicion o funcion del estado siguiente, y para un par del conjunto ExQ devuelve un estado Q.
g:ExQ–>S es la funcion de salida, y para un par del conjunto ExQ devuelve un simbolo de salida del conjunto S.
f y g pueden representarse mediante tablas:
https://drive.google.com/file/d/1AfTgKiYMvTIDV78dxJfvQ_8lXVn6_OcB/view?usp=sharing
Ojo: En las diapositivas siguientes, donde se hacen ejercicios de obtener la gramatica a partir de un autómata, se utiliza esta forma para definir al automata (similar pero no es exactamente la misma):
Quintupla A = (Q, V, δ, q0, F) donde:
Q: Conjunto de estados
V: Vocabulario o alfabeto de entrada
δ: Q x V -> Q funcion de transicion
q0: Estado inicial
F: Conjunto de estados finales.
Esta segunda definicion es mas facil de entender, y es la que se aplica en los ejercicios.
Notacion de elementos (VT,VN,V,Cadenas terminales, Cadenas)
VT: sus elementos se representan por letras minusculas de comienzo de abecedario, operadores, caracteres, digitos del 0 al 9, palabras reservadas de programacion.
VN: sus elementos se representan por letras mayusculas de comienzo de abecedario, excepto el simbolo inicial que va con S. Tambien por nombres en minuscula, pero entre parentesis angulares.
Vocabulario: elementos indiferenciados de VT yVN se denotan con letras mayusculas del final del alfabeto.
Cadenas terminales: cadenas compuestas unicamente por simbolos terminales se representan con letras minusculas del final del alfabeto.
Cadenas: las cadenas que contienen simbolos terminales y no terminales indiferenciados se representan con letras minusculas griegas.
Algoritmo para obtener gramatica regular desde automata finito
1) Asociar a estado incial del automata el simbolo S.
2) Asociar a cada estado del automata un simbolo no terminal (A,B,C).
3) Para cada transicion definida en el automata δ (ei , a) = ej, agregar un elemento al conjunto de producciones, la producción A → 1B, siendo A y B los símbolos no terminales asociados a ei y ej respectivamente. Si ej es un estado final, agregar también la producción A → a.
4) Si el estado inicial es tambien final, agregar la produccion S → ε.
Jerarquia de gramaticas
•Gramáticas de tipo 0:
También llamadas gramáticas no restringidas o gramáticas con estructura de frase.
•Gramáticas de tipo 1:
También llamadas gramáticas sensibles al contexto
•Gramáticas de tipo 2:
También se denominan gramáticas de contexto libre o libres de contexto
•Gramáticas de tipo 3
También denominadas regulares o gramáticas lineales a la derecha comienzan sus reglas de producción por un símbolo terminal, que puede ser seguido o no por un símbolo no terminal
Correspondencia entre lenguajes y gramaticas
Gramatica tipo 0 genera lenguaje tipo 0.
Gramatica tipo 1 genera lenguaje tipo 1.
Gramatica tipo 2 genera lenguaje tipo 2.
Gramatica tipo 3 genera lenguaje tipo 3.
Expresiones regulares
Es una herramienta para describir lenguajes de tipo 3 o regulares.
Son metalenguajes para describir lenguajes regulares.
Operaciones con lenguajes regulares
Union o alternativa:
L1 U L2 = {x/x ∈ L1 🇻 x ∈ L2}
Concatenacion:
L1L2={x1x2/x1 ∈ L1 ∧ x2 ∈ L2}
Potencia de un lenguaje: caso particular de la anterior, concatenas un lenguaje consigo mismo.
Cierre u operacion estrella:
L*={Φ} U {L} U {LL}….
Cierre positivo:
L+={L} U {LL} …..
Operaciones con expresiones regulares
Si ∝ es una expresion regular, entonces {∝} es el conjunto descrito por esa expresion regular.
Union o alternativa:
∝|β es uan exp. reg. tal que {∝|β} = {∝} U {β}.
Concatenacion:
∝β esuna exp. reg. tal que {∝β} = {∝} {β}
Cierre u op. estrella:
∝* es exp. reg que denota {∝}*
Cierre positivo:
∝+ es exp. reg. que denota {∝}+
Propiedades de exp regulares
Asociatividad.
Distributividad respecto a la concatenacion.
lambda es el elemento neutro en concatenacion.
Estado de un automata
Toda la info necesaria en un momento dado para poder deducir, dado un simbolo de entrada en ese momento, cual sera el simblo de salida.
Configuracion y movimiento de un automata
Configuracion: su situacion en un instante dado.
Movimiento: el transito entre dos configuraciones. Se representa con el operador binario –>
Diagramas de Mealy/Moore
Son otra forma de representar las funciones de transicion y saida de un automata (ademas de las tablas).
Son grafos dirigidos en los que:
Cada nodo corresponde a un estado.
Cada transicion se corresponde a un evento.
Por lo tanto, hay una relacion donde para cada par se obtiene el siguiente estado:
(evento, estado actual)–>estado siguiente.
Para la salida:
Maquina de Mealy: la salida esta expresada en los arcos junto al evento. La salida depende del estado y de donde se viene.
Maquina de Moore: la salida esta expresada en los estados. La salida solo depende del estado.
Definicion formal Mealy-Moore
Mealy: 6tupla =(E,S,Q,q0,f,g)
E=vocabulario de entrada
S=vocabulario de salida
Q=conjunto de estados
f: ExQ–>Q mapeo de pares de un estado y simbolo de entrada para el siguiente estado.
g:ExQ–>S mapeo de pares de un estado y simbolo de entrada para el simbolo de salida correspondiente
El de moore es igual, la diferencia esta en g
g(Moore)=Q–>S en este caso solo se mapea el estado al simbolo de salida correspondiente.
Moore vs Mealy
Moore es mas segura de usar, ya que las salidas cambian siempre en el clock, ademas, no todos los circuitos secuenciales se pueden implementar con Mealy, pero si con Moore.
Mealy reacciona mas rapido, ya que las entradas se conectan al combinacional de salida directamente, entonces no espera el clock para cambiar de estado, ademas tienden a tener menos estados justamente por esto.
Automatas conexos, deterministas y no deterministas
Un automata es conexo si todos los estados de Q son accesibles desde el estado inicial q0.
Automata determinista es aquel en el que la funcion de cambio de estafo f es determinista. En caso contrario es no determinista.
Correspondencia entre gramaticas, lenguajes y automatas
Automata tipo 0: maquina de turing. Se corresponde con gramatica y lenguaje (recursivamente enumerable) de tipo 0.
Automata tipo 1: automatas limitados linealmente. Se corresponde con una gramatica y lenguaje (dependiente del contexto) de tipo 1.
Automata tipo 2: automata de pila. Se corresponde con gramatica y lenguaje (libres de contexto) de tipo 2.
Automata tipo 3: automatas finitos. Se corresponde con gramatica y lenguaje (regulares) de tipo 3.
Distintos tipos de automatas
Maquina de Turing: es el mas complejo y potente, se puede ver como una cinta con un cabezal que lee y escribe En el cabezal tenemos los estados, y en la cinta los distintos simbolos. En este caso la cinta se puede mover a izq. o derecha.
Automatas linealmente acotados: Similar a maquina de Turing, pero en este caso la cinta es acotada, no infinita, tiene simbolos # y $ que delimitan a izq. y derecha el limite de la cinta.
Automatas de pila: En este caso la cinta solo se mueve hacia la izquierda, pero el cabezal solo puede leer e ir guardando valores en una pila.
Automatas finitos: los mas simples, en este caso el cabezal solo lee, y la cinta se mueve solo hacia la izquierda.
Maquina de Turing
Cinta infinita con cabezal de lectura escritura. La cinta se puede mover a der. o izq.
En un movimiento puede realizar distintas acciones:
1) cambio de estado
2) imprime simbolo en la sinta reemplazando el simbolo leido
3) se mueve la cabeza en la cinta, o bien se detiene.
Todo esto puede ocurrir de manera conjunta o no.
Definicion formal:
una quintupla MT=(E,S,Q,f,g) (def de automata) o bien la definicion equivalente:
MT=(Q,Σ,Г,δ,q0,B,F) donde:
Q={conjunto de estados}
Г={conj. de simbolos permitidos en la cinta}
B ∈ Г es simbolo blanco
Σ ∈ Г es el subconjunto de simbolos de entrada no incluyendo el blanco
δ: QxГ–>QxГx{I,D,S} es la funcion del siguiente movimiento (Izquierda, derecha, stop).
q0 ∈ Q es el estado inicial
F ⊂ Q es el subconjunto de estados finales.
Una transicion se define como:
r;w,d
donde r es el simbolo que se lee en la cinta
w es el simbolo a escribir sobre la cinta donde esta r.
d es la direccion para mover la cinta luego de escribir w.
Lenguaje aceptado por maquina de Turing
L(MT) es el conjunto de palabras formadas con el alfabeto Σ*. Existe una correspondencia entre gramaticas, lenguajes y automatas de tipo 0 (Maquina de Turing)
Importancia de maquina de Turing
Segun Church:
Algoritmo=Maquina de Turing
Todo algoritmo es equivalente a una maquina de Turing.
Automatas linealmente acotados
Es una maquina de Turing con las siguientes condiciones:
1) el alfabeto de entrada incluye los simbolos # y $ que son las marcas de fin de la cinta.
2) La cabeza del automata no puede desplazarse fuera de esos simbolos, y no puede escribir sobre ellos.
Definicion formal:
ALA=(Q,Σ,Г,δ,q0,#,$,F)
Q=conjunto de estados
Г=Conjunto de simbolos permitidos en la cinta
Σ ∈ Г es el subconjunto de simbolos de entrada no incluyendo el blanco.
δ: QxГ-->QxГx{I,D,S} es la funcion del siguiente movimiento (Izquierda, derecha, stop).
q0 ∈ Q es el estado inicial
F ⊂ Q es el subconjunto de estados finales
# y $ ∈ Σ corresponden a la amrca izq. y der. de la cinta.
Lenguaje aceptado por ALA
Hay correspondencia entre gramaticas de tipo 1, lenguajes de tipo 1 y automatas de tipo 1 (ALA)
Automatas de pila (pushdown automata)
Operaciones elementales:
1)Dependientes de la entrada: se lee un simbolo, y en funcion de este, el estado, y el valor en la pila, el control pasa a otro estado, y en la pila se introduce otro valor, o se extrae el que estaba, o no se hace nada.
2) Independientes de la entrada: si el simbolo que se lee no interviene, la cinta no se mueve, lo que permite amnejar la pila sin la info de entrada.
Definicion formal:
AP=(Q,Σ,Г,δ,q0,Z0,F)
Q=conjunto de estados
Σ=alfabeto de entrada
Г=alfabeto de pila
δ=funcion de transicion, de la forma:
δ: Qx{Σ U {λ}} x Г --> QxГ*
q0 es el estado inicial
Z0 es el simbolo incial de la pila
F es el conjunto de estados finales.
En general este automata es no determinista, es decir que el resultado de la funcion de transicion no esta determinado, pueden resultar dos o mas valores.
Configutacion del automata: situacion en un instante dado, se puede representar por el terceto:
(q,W,∝)
q representa estado actual del automata.
W es la cadena de entrada que resta por analizar.
∝ es el contenido de la pila en ese instante.
En el jflap para describir transiciones:
a,Z;aZ
a es la entrada a procesar
Z es el valor actual en la parte superior de la pila
aZ representa el nuevo valor a empujar en la pila, luego de sacar el valor en la parte superior de esta.
Lenguaje reconocido por automata de pila
Reconocen lenguajes de tipo 2. Existe correspondencia entre gramaticas, lenguajes y automatas de tipo 2 (de pila).
