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.

Tema 2 – Elementos Básicos de un Lenguaje Sistémico

Estructuras de Realimentación Simple

Bucle de Realimentación Negativa

También denominados bucles reguladores o estabilizadores, esta estructura es típica de los sistemas con comportamiento autorregulador. Cualquier modificación en cualquiera de los elementos que forman este tipo de bucles vuelve a él, a lo largo de la cadena, con una acción de signo contrario. En la figura podemos apreciar un diagrama de influencias genérico con realimentación negativa:

Elementos básicos de un bucle de realimentación negativa

Tema 8.4 – Extensiones de la Máquina de Turing Básica

Como en el caso de las técnicas explicadas en el capítulo 8.3, las siguientes extensiones de la MT no conllevan un mayor potencial de reconocimiento de lenguajes. Veremos ahora las MT con varias cintas y las MT no deterministas.

Máquina de Turing con Varias Cintas

Las diferencias entre una MT con varias cintas y una básica (aparte de la obvia diferencia en la cantidad de cintas) son:

Tema 8.3 – Técnicas de Programación para las Máquinas de Turing

A continuación se definirán una serie de técnicas que ayudarán a crear algoritmos más facilmente para las MT. Es importante saber que estas variaciones de la MT convencional no amplían los lenguajes generados.

Capítulo 2 – Procesos vs. Hilos

Procesos

Una forma de programar concurrentemente es dividir un programa en procesos ya que por lo general, los sistemas operativos proveen de un sistema de ejecución concurrente para éstos. Para hacer una comparación entre procesos e hilos aquí se presentan una serie de características de los procesos:

• Poseen espacios de memoria independientes. Algunos sistemas operativos permiten que distintos procesos compartan memoria.
• Pueden encontrarse en diferentes estados. Los cambios de estado (cambios de contexto) son relativamente costosos en términos de tiempo.
• La estructura de los procesos se encuentra en la memoria del núcleo. Esto causa que sea necesario realizar costosas llamadas al sistema para acceder a ella.

Tema 1 – Lenguajes Regulares

Autómatas Finitos, Deterministas y No Deterministas

Autómata finito determinista (AFD): Un autómata finito determinista consiste en una quíntupla (S, Σ, δ, ι, F) donde:

• S es un conjunto finito de estados.
• Σ es el alfabeto de la máquina.
• δ es la función de transición de S x Σ a S. δ(p, x) = q si y sólo si la máquina puede pasar de un estado p a un estado q al leer el símbolo x.
• ι es el estado inicial (elemento de S).
• F es el conjunto de estados de aceptación (subconjunto de S).