Tema 2 – Autómatas de Pila y Lenguajes Independientes del Contexto

Autómatas de Pila

La única diferencia entre un autómata finito indeterminista y uno de pila es que el segundo posee una memoria en forma de pila en la que puede almacenar información para recuperarla más tarde. De modo que los lenguajes aceptados por los autómatas de pila incluyen los lenguajes regulares. Un autómata de pila se define por la séxtupla (S, Σ, Γ, T, ι, F) en la que:

• S es una colección de estados finitos.
• Σ es el alfabeto de la máquina.
• Γ es la colección finita de símbolos de pila. Como convención utilizaremos el símbolo # como indicador de pila vacía.
• T es una colección finita de transiciones. Una transición se define como (p, x, s; q, y) y significa que estando el autómata en el estado p, si lee x de la entrada y s está en la cima de la pila, se extrae s, se inserta y en la cima y se pasa al estado q.
• ι (un elemento de S) es el estado inicial.
• F (un subconjunto de S) es la colección de estados de aceptación.

Capítulo 5 – Regiones Críticas Condicionales

Definición de Región Crítica Condicional

En Pascal-fc podemos declarar una región crítica condicional (RCC) de la siguiente forma:

• resource SC: i, j; → Lo que significa que se declara la RCC SC compuesta por las variables i y j. Estas dos variables no podrán pertenecer a otra RCC distinta a SC.

Así las variables que componen una RCC solo podrán ser referenciadas dentro de la construcción region. De esta forma resolvemos el problema de la exclusión mutua.

Capítulo 4 – Semáforos

Definición de Semáforo

Los semáforos pueden realizar tres operaciones: wait, signal y initial. Estas operaciones son atómicas, de modo que sólo un proceso podrá estar ejecutándolas sobre un semáforo en determinado momento.

• wait(s): Decrementa el valor del semáforo s. Si s es 0 bloquea el proceso que realiza la llamada. Es importante saber que, según la implementación, cuando un proceso realiza esta llamada puede, decrementar s sin importar su valor o decrementarlo sólo si es mayor que 0. Así s podrá tener valores negativos o no según como se haya implementado.
• signal(s): Si hay algún proceso bloqueado lo desbloquea y si s permite valores negativos lo incrementa. Si no hay procesos bloqueados solamente incrementará el valor de s.
• initial(s, v): Inicializa el valor de s a v. Esta operación es específica de Pascal-fc, donde la implementación de los semáforos no permite valores negativos.

Se asume que los procesos bloqueados se insertan en una cola FIFO (First In First Out), así el primero en ser bloqueado es el primero que se desbloquea.

Tema 8.5 – Máquinas de Turing con Restricciones

Presentaremos a continuación una serie de variaciones de la MT básica que, a diferencia del capítulo 8.4, presentan diversas limitaciones pero, como en las variaciones introducidas anteriormente, siguen generando lenguajes recursivamente enumerables.

Máquinas de Turing con Cintas Semi-infinitas

A diferencia de la MT básica, cuya cinta es infinita hacia la izquierda y la derecha, este tipo de MT es infinita hacia la derecha pero tiene un límite a la izquierda (se puede hacer un símil con el conjunto de los números naturales). La posición inicial de la cabeza es en el extremo izquierdo de la cinta, por lo que no hay casillas a la izquierda de la cabeza. Además les pondremos una restricción más a estas MTs: no pueden escribir espacios en blanco.

Capítulo 3 – Primeras Aproximaciones a la Solución de los Problemas de la Programación Concurrente

Tipos de Sincronización y su Solución

Los dos tipos de sincronización necesarios entre procesos concurrentes son la exclusión mutua y la condición de sincronización definidos en el capítulo 1. Cuando se hable de procesos se asume que también se habla sobre los hilos.

Exclusión Mutua

Cuando un proceso se encuentra en su sección crítica, el resto de procesos no podrá estar en esa misma sección y si quisieran acceder a ella deberán esperar a que quede libre. Cuando un proceso termina de ejecutar su sección crítica se deberá permitir que otro proceso en espera entre en la sección.