Resumen SSL

MSV

UNIDAD N°1 – Introducción a la Teoría de Autómatas y Lenguajes Formales

1. Máquinas Abstractas y Gramáticas Formales
Máquinas  Autómatas  dispositivos formales capaces de exhibir conductas que han sido previamente
determinadas.
 Abstractas  no necesariamente existen como objetos materiales; son conceptualizaciones que se utilizan para el
diseño, la implementación y evaluación de algoritmos, el análisis de su complejidad, la evaluación de los recursos
necesarios para determinado cómputo, etc.
Lenguajes: se distinguen en dos:
 Naturales  evolucionan según usos y costumbres.
 Formales  son desarrollados a partir de gramáticas previamente establecidas y no admiten forma alguna de
excepción o desviación.
La teoría de los lenguajes y gramáticas formales es revolucionada por el lingüista Noam Chomsky en 1956, con la
presentación de su trabajo “Teoría de las Gramáticas Transformacionales”. Estableció las bases de la lingüística
matemática, proporcionando una herramienta aprovechada en la formalización de los entonces incipientes lenguajes
de programación.
El concepto de máquina fue cambiando en la historia. Se destacan:
• Blaise Pascal (1640) – primera máquina sumadora de la historia.
• Claude Shannon (1938) – implementación de las centrales telefónicas con circuitos eléctricos.
• Autores varios (act.) – implementación de autómatas a través de software, comunicándose con el medio exterior.
Se destaca Alan Turing, quien en 1936 propuso una máquina abstracta, hoy llamada Máquina de Turing.
La MT es un formalismo propuesto para disponer de una herramienta más abstracta para estudiar la teoría de la
computabilidad. Turing tomó las ideas del matemático Gödel y demostró que existen problemas irresolubles, aquellos
fuera del alcance de su máquina, capaz de resolver cualquier problema que tuviese solución.
2. Características y Formalismos de las Máquinas Abstractas (MA).
Todas las MA comparten las siguientes características comunes:
a. Reconocen que el tiempo avanza en forma discreta, de intervalo en intervalo.
b. En c/int., se encuentran en un cierto y único estado. El conjunto de estados es finito, agrupado en un alfabeto de
estados.
c. Reciben información o estímulos del medio exterior, incorporando el concepto de cinta de entrada. En cada IT
la MA lee un símbolo de la cinta de entrada. El conjunto de los símbolos reconocidos por la MA se agrupa en un
conjunto llamado alfabeto de entrada.
d. Pueden actuar sobre el medio exterior, grabando símbolos en una cinta de salida. Pertenecen a un alfabeto de
salida, y la cinta puede ser misma que la de entrada o no, dependiendo de la máquina.
e. Las lecturas/escrituras en cada IT se realizan mediante cabezales, que se desplazan sobre los medios de E/S. Se
distinguen las máquinas según si los cabezales se mueven en un mismo sentido o si se puede gobernar su mov.
f. Definen sus aptitudes en la llamada función de transición. Define para cada símbolo de entrada y estado
posible el próximo estado a ser adoptado, además del sentido del cabezal y el símbolo de salida.
Es pertinente mencionar que las cintas representan la posibilidad de que una MA lea datos del medio y genere salidas
sobre el mismo. Además, la FT puede ser completa/total o parcial, cuando no se definen ciertos estados en los que la
MA no se encontrará nunca. En caso de que llegase a tal instancia, se asume que la MA se detendrá.
También se las conoce como máquinas de estado/estímulo-respuesta, al tratarse de sistemas reactivos que
operan en respuesta a los sucesivos estímulos del medio, adoptando estados y enviando respuestas al exterior.
3. Clasificación de las Máquinas Abstractas
Traductoras → establecen una relación entre las cadenas de entrada y las de salida.
Reconocedoras → validan o aceptan ciertas cadenas de E, arribando a estados finales llamados de aceptación, sin
producir cadenas de salida.
Autómatas Finitos → comienzan su operación en un estado conocido (EI) y completan su ciclo arribando a un estado
de aceptación (EA), empleando una cantidad finita de IT (comportamiento logarítmico).
Máquinas Secuenciales → no tienen previstos EI y, en algunos casos, tampoco tienen definidos EA. Es decir, operan
de forma ininterrumpida, sin reconocer condiciones específicas para iniciar y terminar su actividad.
Autómata Determinista → su conducta está completamente determinada por su función de transición.
Autómata No Determinista → su conducta presenta indeterminaciones puesto que su función de transición prevé más
de un próximo estado para cierta condición de estado y entrada. Además, pueden realizar transiciones sin leer ningún
símbolo.
4. Automatismos y Autonomía
Los autómatas exhiben comportamientos automáticos, es decir que han sido establecidos con anticipación al
momento de su diseño y construcción, y su modificación está fuera del alcance del propio autómata. Son
automatismos que para ser dotados de un comportamiento diferente deben ser rediseñados.
Autonomía implica la capacidad de alterar por sí solo el propio comportamiento y esto surge de la interacción
del sistema con su entorno. Los sistemas autónomos comienzan a operar como automáticos y se distinguirán de estos
últimos de manera progresiva, a lo largo de su operación.
Para que una ME tenga comportamiento autónomo debe ampliar su alfabeto de entrada de manera dinámica. Las
máquinas que exhiban autonomía pueden ser calificadas como inteligentes. Se distinguen entonces:
• El comportamiento de los sistemas automáticos está completamente predeterminado.
• Para que un sistema sea autónomo debe ser antes automático.
• En los sistemas autónomos el comportamiento es una propiedad emergente de la interacción del sistema y su
ambiente.
5. Jerarquía de Máquinas y Gramáticas
Los autómatas finitos y las MT representan los dos extremos de una jerarquía creciente en complejidad y capacidad.
La MT, al ser capaz de resolver todo problema que tenga solución, representa el límite natural de lo computable.

Se distinguen los roles de las gramáticas y los autómatas o máquinas:

Gramáticas → son metalenguajes, destinados a la generación de los lenguajes formales.
Autómatas/Máquinas → son modelos de entidades reconocedoras de esos lenguajes.
El lenguaje es el vínculo que establece un isomorfismo entre ambas.
Chomsky utilizó las formas que toman las reglas de producción de las gramáticas para proponer una clasificación
en cuatro tipos, en las que las menos restringidas incluyen sucesivamente a las siguientes.

El vínculo de la jerarquía de Chomsky y la familia de máquinas abstractas se describe de la siguiente manera:

Autómata Finito – Gramáticas Regulares

El autómata muestra sus principales componentes, que son: un
conjunto de estados (p, q, r, etc.), su función de transición f,
una cinta que contiene símbolos del alfabeto de entrada (a, b,
c, d, etc.) y su cabezal de lectura, que se mueve en un mismo
sentido con el fin de leer secuencialmente la cadena a ser
procesada.
Autómata Finito Bidireccional – Gramáticas Regulares
Al posibilitar que el sentido del movimiento del cabezal de
entrada sea controlado por la propia máquina, obteniéndose
el AFBD. La función de transición debe ser ampliada para
incorporar la definición del movimiento del cabezal. Además, la
cadena de datos a ser procesada es contenida entre dos
símbolos especiales (├ y ┤) destinados a limitar el movimiento
del cabezal sobre la cinta.
El AFBD no incrementa su capacidad y se mantiene vinculado a las gramáticas regulares
Autómata con Pila – Gramáticas Independientes del Contexto
Al AF se le agrega una memoria LIFO, se obtiene el AP. Se hace necesario definir el alfabeto vinculado a la pila, que
puede tener símbolos en común con el alfabeto de entrada,
y en el que se debe identificar un símbolo destinado a señalar
el fondo de la pila (en el ejemplo de la figura, se utiliza el #).
La función de transición debe ser ampliada para incorporar
como argumento el símbolo leído de la pila y para prever la
salida sobre ella.
Autómata Linealmente Acotado – Gramáticas Dependientes del Contexto
Si se agrega la posibilidad de grabar sobre la misma cinta
de entrada, se obtiene una nueva máquina que incrementa
notablemente su capacidad, el ALA. Esto implica ampliar la
función de transición para incorporarle la definición del
símbolo que es grabado en cada caso. Es decir que esta
función ahora define el próximo estado, el símbolo grabado y el sentido del movimiento del cabezal.
Máquina de Turing – Gramáticas sin Restricciones
Si se eliminan los límites en los extremos de la cinta
de entrada / salida, permitiendo el acceso a un espacio
ilimitado que puede ser usado como un área auxiliar de
almacenamiento. Se llega así a la máquina de Turing,
que es capaz de resolver cualquier problema que tenga
solución, es decir que sea computable. Como es de
esperar, esta máquina está relacionada con todas las gramáticas, incluyendo la última en la escala de Chomsky que
no tiene restricciones.

UNIDAD N°1 – Anexo – Compiladores

1. Consideraciones generales
El compilador es una herramienta de desarrollo de software destinada a traducir un programa escrito en un
lenguaje de alto nivel (programa fuente) en otro programa escrito en lenguaje máquina (programa objeto).
En sus inicios, los computadores debían ser programados con códigos binarios que representaban las instrucciones
individuales reconocidas por la unidad central de proceso, llamados “Lenguajes de Primera Generación”.
Posteriormente, el código de máquina fue reemplazado por nombres simbólicos o “abreviaturas nemónicas”, dando
lugar así a los “Lenguajes de Segunda Generación/Ensambladores”. Para sustituirlos, se crearon los “Lenguajes de
Tercera Generación/de Alto Nivel”, que permitieron alcanzar un mayor nivel de abstracción, apropiado para la
especificación de datos, funciones y su control, e hicieron posible una rápida evolución de la programación con la
incorporación de técnicas orientadas a la obtención de menores tiempos de desarrollo y mayor claridad en el código.
Se mencionan Fortran y Cobol.
2. Conceptos relacionados
Editor de programas: Los programas fuentes son archivos de texto, no estructurados, que contienen el código
expresado en un lenguaje superior. Esta información debe ser cargada por el usuario, almacenada, ordenada y
presentada visualmente al programador a partir de un estructuramiento lógico. Se trabajan con el Editor de Programas.
Compilación: Se refiere al proceso de convertir un programa fuente en un programa objeto, para lo cual el compilador
comienza por verificar la integridad y ausencia de errores del primero.
Compilación en varias pasadas: Define la cantidad de veces que un compilador debe leer el programa fuente previo
a la generación del programa objeto.
Intérprete: herramienta o módulo que interpreta y ejecuta las sentencias de un programa fuente una tras otra, sin
generar un programa objeto.
Preprocesador: módulo que tiene la finalidad de modificar o completar al programa fuente previo a ser leído por el
compilador. Conceptualmente, el preprocesador es un módulo independiente del compilador, aunque es frecuente que
estén implementados en forma conjunta.
Conversor Fuente-Fuente: Tienen por finalidad la conversión de un programa fuente desde un lenguaje de alto nivel
a otro. Su finalidad es facilitar a los nuevos usuarios la migración de un lenguaje a otro.
 Ensamblador: Se denomina así a un compilador que tiene por lenguaje fuente a uno de 2ª generación, por lo que se
trata de un procesador sencillo que guarda una relación 1 a 1 entre entrada y salida.
Administrador de librerías: herramienta que permite gestionar en una librería las partes de un sistema que han sido
compiladas por separado y que están destinadas a integrar una aplicación.
Depurador: Llamado debugger en su idioma original, es un módulo usado para facilitar las pruebas y eliminar errores
de los programas.
Enlazador: Llamado task builder o linkeditor en su idioma de origen, tiene la misión de construir el programa ejecutable
a partir del programa objeto, las librerías que pueda tener la aplicación y la librería del sistema operativo. Esta última
suele ser reconocida como run time library. El programa ejecutable es almacenado en un archivo cuya estructura y
denominación (normalmente extensión EXE) son acordes a las exigencias específicas de cada sistema operativo.
Librería de enlace dinámico: librerías que son incorporadas a la aplicación en tiempo de ejecución cuando son
necesarias. Podrían ser consideradas una extensión del programa ejecutable y son llamadas Dynamic Link Libraries
en su idioma de origen. La extensión de estos archivos es DLL y normalmente contienen la mayor parte de las
facilidades que ofrecen los sistemas operativos. Permiten que componentes básicos sean compartidos por numerosas
aplicaciones y reducen el tamaño de los archivos de los sistemas.
3. Tipos de Compiladores
Nombre Definición
Compilador Genera programas objeto que están destinados a ser ejecutados en computadoras diferentes de aquel en
Cruzado que se lo ha compilado.
En su propio programa fuente está escrito en el mismo lenguaje que el de los programas fuentes que
Autocompilador
admite.
Compilador capaz de admitir programas fuentes escritos en diversos lenguajes. Se debe identificar la
Metacompilador
variante del lenguaje fuente a ser utilizada. Ej: MetaAssembler.
Módulo destinado a operar en el sentido inverso al de un compilador, e.d, convertir programas escritos en
Decompilador
lenguaje máquina a programas fuentes en lenguajes de alto nivel. Ej: desensambladores.
Al generar el programa objeto se tiene en cuenta la necesidad de mejorar el rendimiento del sistema,
Compilador
manteniendo la funcionalidad original. Tiene como objetivos la reducción del tamaño del ejecutable, la
optimizado
demanda de memoria y la rapidez de operación.
Compilador Admiten programas objeto representados en forma simbólica; normalmente como esquemas lógicos o
gráfico eléctricos. Ej: Controladores Lógicos Programables (PLC)
Generan los programas objeto en un lenguaje intermedio, que luego son interpretados en el momento de
Compilador
la ejecución. Se obtiene total transportabilidad de los programas objeto ya que las particularidades de las
intérprete
plataformas son incorporadas en la etapa de interpretación.
Ambiente Son sistemas interactivos que incorporan al compilador servicios complementarios, tales como un editor
Integrado de de programas fuentes, facilidades para interpretar los programas y ejecutarlos paso a paso o en forma
Desarrollo (IDE) parcial, identificar errores (depuración o debugging) y gestionar las librerías de los proyectos.

4. Compiladores e Intérpretes
Si bien la evolución tecnológica que lleva al uso de uno u otro, se mencionan las principales diferencias:
• Un compilador siempre crea un programa objeto de un programa fuente correcto y un intérprete nunca lo crea
• Un intérprete lee y ejecuta los programas en forma progresiva, sin necesidad de cargar en la memoria al programa
fuente completo ni la de generar luego en memoria un programa objeto.
• La rapidez de ejecución es la principal desventaja de los intérpretes.
 5. Notación T
Todo compilador involucra tres lenguajes de programación:
1. el del programa fuente “F”, que se desea compilar
2. el del programa Objeto “O”, que se desea generar
3. el lenguaje de implantación “I”, que es aquél en el que el propio compilador
fue escrito
Esto resulta convenientemente representado con un esquema denominado Notación T, propuesta por H. Bratman, que
permite representar el vínculo entre los tres lenguajes.
6. Contexto del Compilador
Incluye los diversos recursos necesarios para hacer posible la
generación de programas ejecutables a partir de los correspondientes
programas fuentes. Toman la forma de módulos o herramientas de
desarrollo. La totalidad de los componentes que están incluidos en el
contexto de un compilador forman parte de los ya definidos Ambientes
Integrados de Desarrollo (IDE).

7. Estructura y Componentes del Compilador

Se distinguen dos etapas principales, que son las de análisis y de síntesis. En
la etapa de análisis, se divide el programa fuente en sus elementos componentes
y se crea una representación intermedia del mismo. En la etapa de síntesis, se
reconstruye el programa objeto a partir de esta representación intermedia.
Sin embargo, el proceso de compilación reconoce el cumplimiento de seis fases
claramente distinguibles desde un punto de vista conceptual.
• La etapa de análisis es dependiente del lenguaje del programa fuente y la
etapa de síntesis lo es del tipo de procesador al que está destinado el
programa objeto.
• Con solo combinar distintas etapas de análisis con una misma etapa de
síntesis se pueden construir compiladores para varios lenguajes fuentes
destinados a un mismo procesador.
• Combinando una etapa de análisis con diferentes etapas de síntesis se
dispondrá de compiladores de un mismo lenguaje fuente destinados a
diferentes procesadores.
Análisis Léxico
 La cadena de caracteres que constituye el programa fuente es leída carácter a carácter, para identificar y agrupar sus
componentes léxicos.
 Estos componentes léxicos son secuencias de caracteres (cadenas) que tienen un significado colectivo y son denominados
tokens.
 Una cadena de caracteres específica que se ajuste al patrón léxico de un cierto tipo de token es denominada lexema
 El módulo destinado a esta tarea es denominado analizador lexicográfico o scanner.
Análisis Sintáctico
 Se reciben las secuencias de componentes léxicos que fueron identificadas en la fase anterior, y debido a que las
combinaciones de estos componentes dan lugar a sentencias del programa fuente, es necesario comprobar que
las sentencias sean sintácticamente correctas, e.d, se debe verificar que todas las sentencias puedan haber
sido generadas por la gramática del lenguaje fuente.
 En caso contrario, el analizador debe informar sobre los errores sintácticos detectados de manera precisa e
inteligible.
 Está a cargo de los analizadores sintácticos.
 Todo analizador sintáctico destinado a reconocer un lenguaje libre de contexto tiene una capacidad computacional
equivalente a la de un autómata con pila.
Análisis Semántico
 Se revisa al programa fuente, sintácticamente correcto, para reunir información sobre los tipos de las variables
que será utilizada en la fase posterior de generación de código intermedio.
 Se procuran identificar eventuales errores semánticos.
 Las comprobaciones aquí son denominadas estáticas (p/dif/dinámicas) e incluyen detección y comunicación de
errores de diversas naturalezas:
o comprobación de tipos
o comprobación de flujos de control
o comprobación de unicidad o coherencia en las denominaciones de identificadores
o coherencia en los argumentos de subprogramas
o potenciales errores en tiempo de ejecución (variables no inicializadas, direccionamiento de arreglos fuera de
límites, cocientes que pueden tomar valores nulos, etc.).
Generación de Código Intermedio
La etapa de análisis prepara al programa fuente para ser convertido en un nuevo programa escrito en un lenguaje
elemental que es normalmente denominado lenguaje intermedio. Tradicionalmente, fue utilizado el código de tres
direcciones –sus instrucciones incluyen tres registros, dos de ellos para operandos y el tercero para el resultado–.
Con la evolución de los lenguajes de alto nivel, se procuró normalizar este lenguaje intermedio y la tendencia fue
adoptar un lenguaje universal denominado Uncol (Universal Compiler Oriented Language).
De esta manera, se facilita la combinación de módulos destinados a interpretar diversos lenguajes fuentes (etapa de
análisis) con los de la etapa de síntesis destinada a producir código para diversos lenguajes objeto. Esta normalización
significa un inmenso ahorro en el esfuerzo de programación y la posibilidad de acortar significativamente los tiempos
requeridos para la presentación de nuevos productos y herramientas de programación.
Optimización de Código
Esta fase realiza una mejora en la calidad y eficiencia del código intermedio, pero difícilmente permita alcanzar un
código óptimo. Para ello se comienza a identificar las zonas críticas del programa
Al efectuarse las mejoras requeridas por el proceso de optimización, se sigue un orden que es el siguiente:
1) Mejoras que se refieren a la calidad de la implementación del programa desde el punto de vista lógico.
2) Mejoras particulares para el mejor aprovechamiento global de una cierta máquina, como son la selección de las
instrucciones más apropiadas, direccionamientos, etc.

Generación del Programa Objeto

Se toma como entrada a la representación intermedia y se produce un programa objeto equivalente, que debe ser
correcto, eficiente, apropiado a la máquina en la que se va a operar y apto para dar lugar a un ejecutable compatible con
el entorno. Sus tareas son:
i) selección del orden de evaluación de expresiones, ii) selección de instrucciones de la máquina de destino, iii) asignación
de registros, memoria y otros recursos y iv) administración de la memoria para datos y programa.
8. Gestor de la tabla de Símbolos
Es un administrador de una base de datos que contiene los identificadores del programa fuente y sus atributos.
En las fases de análisis, esta base es definida y completada, para servir luego de consulta en las fases de síntesis.
Esta tabla contiene un registro por cada identificador y es cargada a medida que el analizador léxico detecta nuevos
elementos en el programa fuente. Posteriormente, los restantes atributos de cada identificador son definidos en las
fases de análisis sintáctico y semántico. Entre los atributos pueden mencionarse los siguientes: i) identidad (constante,
variable, arreglo, función, rótulo, etc.), ii) tipo (entero, real, carácter, cadena, etc.), iii) dimensiones (para el caso de un
arreglo), iv) argumentos (para el caso de función o subprograma) y v) dirección de memoria asignada.
9. Identificación y Gestión de Errores
El gestor de errores, esencialmente activo en las fases de análisis, detecta los errores, los asocia a determinada
línea del programa fuente e intenta su recuperación con la finalidad de proseguir con la tarea de compilación.
Para esta última tarea, el registrador dispone de un corrector lexicográfico, un corrector sintáctico y un corrector
semántico, que operan según la fase en la que fue reportada la irregularidad.
Dentro los posibles tipos de errores que pueden darse, se mencionan:
• Errores de programación.
• Errores lexicográficos → símbolos incorrectos en lugares incorrectos.
• Errores sintácticos → estructura del programa no respeta las reglas.
• Errores semánticos → errores de tipos, argumentos de funciones, etc.
• Fallas en el compilador → excede los límites del compilador.
• Errores de ejecución → lógica, periféricos, imprevisiones, etc.
Dentro de las consecuencias de los errores, se mencionan:
 Errores en tiempo de compilación.
 Errores que interrumpen la ejecución.
 Errores que afectan los resultados.
UNIDAD N°2 – Introducción a la Teoría de Autómatas y Lenguajes Formales
1. Introducción a los lenguajes
Lenguaje → conjunto de signos (o palabras) y de reglas que los organizan.
El signo es un concepto abstracto que permite hacer referencia a objetos. El proceso por el cual se toma un objeto
como signo de algo se denomina interpretación. Sin interpretación no hay signo. Un símbolo es un signo creado
convencionalmente.
Se llama denotado al objeto al que se refiere el signo y designado a las características o propiedades a las que se
remite el signo. El hecho de que un signo tenga más de un designado se denomina ambigüedad.
En cuanto a las reglas, que son las relaciones entre los signos de los lenguajes, se distinguen:
1. Sintácticas: establecen el orden y relación entre los signos.
2. Semánticas: relacionan los signos y sus significados.
3. Pragmáticas: vinculan los signos con sus usuarios.
Al unir las tres, obtenemos la sintaxis del lenguaje que, sumada a la morfología –que estudia la forma que toman las
palabras– y la fonética –su expresión oral–, se obtiene la composición de la gramática de los lenguajes.
2. Símbolos, alfabetos y palabras
Las computadoras actuales y todos los dispositivos digitales solo almacenan dos señales diferentes. Con solo dos
señales y una adecuada codificación (UNICODE, ASCII, etc.) se puede representar cualquier conjunto de símbolos,
tales como:
1. Letras de algún alfabeto humano (o algunos).
2. Caracteres especiales de control de dispositivos electrónicos
3. Dígitos y símbolos especiales.
Alfabeto
Se denomina alfabeto a cualquier conjunto finito y no vacío de símbolos. Se los denota con letras griegas
mayúsculas Σ, Γ, Λ, Ω acompañada o no de un subíndice. Como se trata de un conjunto, goza de las sig. propiedades:
 Dos alfabetos son iguales si y solo si tienen exactamente los mismos símbolos, sin considerar el orden de
presentación o las repeticiones que pudieran mostrarse.
 Si todos los símbolos de un alfabeto Ω1 están también en otro alfabeto Ω2 , se dice que el primero está incluido en
el segundo y se lo denota 𝛀𝛀𝟏𝟏 ⊆ 𝛀𝛀𝟐𝟐 (inclusión amplia); también se dice que Ω1 es un subconjunto de Ω2 .
o Si además, el segundo alfabeto posee al menos un símbolo que el primero no tiene, se dice que el primero
está estrictamente incluido en el segundo, denotándose en este caso 𝛀𝛀𝟏𝟏 ⊂ 𝛀𝛀𝟐𝟐 (inclusión estricta); se
expresa en este caso que 𝛀𝛀𝟏𝟏 es un subconjunto propio de 𝛀𝛀𝟐𝟐 .
 El cardinal de un alfabeto dado Ω, denotado |Ω|, es la cantidad de símbolos que el mismo posee y siempre será,
por definición, un número entero positivo.
Palabra, cadena o string
Una palabra definida sobre un alfabeto Σ es cualquier secuencia finita de símbolos de 𝚺𝚺, escritos uno a
continuación del otro, es decir, concatenados. Se usarán letras griegas minúsculas 𝛼𝛼, 𝛽𝛽, 𝛾𝛾, 𝛿𝛿, 𝜔𝜔, … con o sin subíndices
para nombrarlas.
Las palabras pueden a su vez concatenarse entre ellas para formar nuevas palabras. La concatenación no es
conmutativa pero sí es asociativa.
Se le llama potenciación de símbolos de un alfabeto a la notación dada a una palabra que se forma como la
concatenación de un símbolo consigo mismo, definido recursivamente como:

donde a es un símbolo del alfabeto, n ∈ ℕ es un número natural y 𝜆𝜆 denota la cadena sin símbolos (cadena vacía).
Longitud de una palabra
La cantidad de símbolos que conforman una palabra es llamada su longitud o largo y se denota con el nombre de
la cadena entre barras verticales.
Cadena vacía
Se denota con 𝜆𝜆 (lambda) a la palabra vacía, palabra que no tiene símbolos y cuyo largo es cero: |𝜆𝜆| = 0.
La palabra vacía resulta ser así, elemento neutro respecto de la operación de concatenación entre palabras,
cualquiera sea el alfabeto sobre el cual las palabras estén definidas. En símbolos:
∀Σ: ∀α definida sobre Σ: α ° λ = λ ° α = α
λ es la única palabra con estas propiedades (matemáticamente, el conjunto de todas las cadenas de símbolos de Σ
junto a la operación de concatenación, conforman un semigrupo con elemento neutro λ).
La concatenación de una palabra consigo misma permite definir la potencia enésima de una palabra como la
concatenación n veces de la palabra consigo misma; recursivamente, si α es una palabra definida sobre algún alfabeto
Σ y n ∈ ℕ es un número natural, entonces su potencia enésima es:

Si bien la potenciación de palabras está definida para números naturales, se acepta la notación α−1 para denotar a la
palabra refleja de una cadena 𝛂𝛂, obtenida escribiendo los símbolos de α en orden inverso.
Supongamos que una cadena puede escribirse como concatenación de otras tres, digamos 𝛚𝛚 = 𝛂𝛂𝛂𝛂𝛂𝛂; entonces
decimos que 𝛂𝛂 es un prefijo de 𝛚𝛚 (primera parte de omega), que 𝛃𝛃 es un sufijo de 𝛚𝛚 (última parte de omega) y que
𝛘𝛘 es una subpalabra de 𝛚𝛚 (una parte de omega). Aquí, cualquiera de las tres cadenas 𝛂𝛂, 𝛘𝛘 o 𝛃𝛃 pueden ser vacías.
De un sufijo o prefijo de una palabra se dice que es propio si no es la misma palabra en cuestión o la palabra vacía.
Operaciones con alfabetos
Al ser conjuntos, cuentan con las propiedades de:
- Unión → Σ1 ∪ Σ2 = {todos los símbolos comunes y no comunes a ambos alfabetos}
- Intersección → Σ1 ∩ Σ2 = {todos los símbolos comunes a ambos alfabetos}
- Resta → Σ1 − Σ2 = {todos los símbolos del primero que no estén en el segundo}
- ���1 = {se debe definir el universo contra el cual complementar}
Complemento → Σ
- Concatenación → Σ1 ∘ Σ2 = {se concatena cada símbolo de Σ1 con Σ2 en ese orden}
Se define recursivamente la potenciación de un alfabeto (lo que permite obtener conjuntos de palabras de largo n
formadas con los símbolos de este), de la siguiente forma:

Se denomina universo de discurso de un alfabeto 𝚺𝚺 al conjunto de todas las palabras que pueden formarse con
sus símbolos. También se lo llama lenguaje universal de Σ, suele denotarse 𝐖𝐖(𝚺𝚺) y con mayor frecuencia 𝚺𝚺 ∗ , que se
lee estrella de Kleene de sigma.
Está compuesto de todas las cadenas de símbolos de sigma de largo cero, todas las de largo uno, de largo dos y así
sucesivamente (utilizando las potencias sucesivas del alfabeto Σ). Queda entonces:

o resumidamente
La estrella de Kleene de un alfabeto también recibe el nombre de cierre o clausura del alfabeto (reflexiva y transitiva)
del alfabeto; si se quita la unión de la potencia cero, e.d, eliminar la palabra vacía, se obtiene:

Es decir, el conjunto de todas las palabras de símbolos de Σ de largo uno o mayor, denominado cierre positivo del
alfabeto 𝚺𝚺.

3. Lenguajes y Operaciones
Lenguaje
Un lenguaje definido sobre un alfabeto es un conjunto de palabras construidas con los símbolos de ese alfabeto.
En símbolos, si Σ es un alfabeto y L es un lenguaje definido sobre Σ, entonces
∗
𝐋𝐋 ⊆ 𝚺𝚺
Al ser los lenguajes conjuntos de palabras, poseen las siguientes propiedades:
• Un lenguaje 𝐋𝐋𝟏𝟏 definido sobre Σ es subconjunto de otro 𝐋𝐋𝟐𝟐 si toda palabra de 𝐋𝐋𝟏𝟏 es también palabra de 𝐋𝐋𝟐𝟐 :

Operaciones con lenguajes

Descripción de Lenguajes
Como todo conjunto, un lenguaje puede definirse o determinarse:
• Por extensión o enumeración, indicando una por una todas las palabras que son elementos de este.
• Por comprensión, explicitando propiedades de las cadenas definidas sobre algún alfabeto, que solo las palabras
del lenguaje verificarán. Dentro de esta, se encuentran las formas:
o Coloquialmente: propiedades explicitadas en lenguaje natural.
o Conjunto con una propiedad: propiedades dadas en símbolos.
o Fórmula lingüística o algebraicamente: propiedad expresada utilizando potenciaciones, uniones,
intersecciones, concatenaciones, etc.
4. Gramáticas Formales
Reglas de reescritura o producciones
Para un alfabeto Σ diremos que una producción o regla de reescritura es un par ordenado de palabras(𝛂𝛂, 𝛃𝛃)
definidas sobre Σ. Se escriben las producciones con la forma BNF:
𝛂𝛂 ≔ 𝛃𝛃
Donde diremos que la cadena 𝛂𝛂 es el lado izquierdo de la producción, := el símbolo de la producción y la cadena 𝛃𝛃 su
lado derecho. Se lee como alfa produce beta o alfa puede reescribirse como beta.
Uso de las producciones
1) Se llama derivación directa a la operación que aplica una sola producción a una palabra obteniendo una nueva,
simbolizada como
𝛅𝛅 → 𝛗𝛗
Se dice que δ se deriva directamente en φ; o que φ se obtiene por derivación directa desde δ por la aplicación de una
producción.

2) Se llama sencillamente derivación a la operación de aplicar una secuencia finita de producciones a una cadena
δ dada para obtener otra cadena φ, y se simboliza:
𝛅𝛅 →∗ 𝛗𝛗

Si durante el proceso de derivación, cada vez que puede optarse por una producción a aplicar se efectúa el reemplazo
posible más a la derecha en la cadena, se dice que se ha efectuado una derivación por la derecha. Si el reemplazo
que siempre se elige es el de más a la izquierda posible, se dice que se ha hecho una derivación por la izquierda.
En los casos en los que las opciones se toman mezcladas, la derivación puede denominarse mixta.

3) Se llama reducción directa a la operación inversa de una derivación directa.

Así, se dice que φ puede reducirse a δ si existe una producción que aplicada a δ la transforma en φ, y se simboliza:
𝛅𝛅 ← 𝛗𝛗
Si lo que se hacen son múltiples reducciones directas para descubrir o revertir una derivación completa, simplemente
se dice que se hizo una reducción y se la denota:
4.1 Gramática Formal
Una gramática formal G es una cuádrupla (𝚺𝚺𝐓𝐓 , 𝚺𝚺𝐍𝐍 , 𝐒𝐒, 𝐏𝐏) en la cual sus cuatro componentes representan:
𝚺𝚺𝐓𝐓 → es el alfabeto de los símbolos que formarán las cadenas del lenguaje que se está describiendo y es denominado
alfabeto de símbolos terminales.
𝚺𝚺𝐍𝐍 → es un conjunto de variables o símbolos auxiliares llamado alfabeto de símbolos no terminales.
𝐒𝐒 ∈ 𝐍𝐍 →es un símbolo no terminal distinguido denominado axioma o símbolo inicial de la gramática.
𝐏𝐏 es un conjunto de producciones de la forma α ≔ β donde ambas palabras están compuestas de símbolos
terminales y símbolos no terminales, pero en α al menos debe encontrarse un símbolo no terminal.
Se debe destacar que:
- Todas las cadenas descriptas por la gramática estarán
construidas con los símbolos del alfabeto de símbolos
terminales.
- Los símbolos no terminales sirven para armar las
producciones pero nunca aparecerán en las cadenas del
lenguaje definido por la gramática, por ello son también
llamados auxiliares. ΣT ∩ ΣN = ∅
- Para un mismo lenguaje puede existir más de una gramática que lo describa, pero todas estas descripciones tendrán
exactamente los mismos símbolos terminales.
- Las producciones del conjunto P son las reglas que permiten, a partir de derivaciones desde el símbolo inicial S de la
gramática, generar las palabras del lenguaje descripto.
En el contexto de las gramáticas formales de Chomsky, las producciones siempre deben tener en el lado izquierdo
al menos un símbolo no terminal, porque es ese símbolo el que se reescribe o remplaza en general en una derivación
directa.
Lenguaje Generado
Si se aplica alguna producción al axioma para transformarlo en una cadena de símbolos terminales y no terminales, y
luego al resultado obtenido se le vuelve a aplicar una producción reescribiendo algún no terminal como una cadena de
terminales y no terminales y se sigue con este proceso hasta que todos los símbolos que queden sean terminales, se
obtiene una cadena de terminales como una derivación desde el axioma. Todas las combinaciones y órdenes posibles
de aplicación de producciones crearán de esta forma, un conjunto de cadenas de símbolos terminales bien definido.

Equivalencia de Gramáticas
4.2 Jerarquía de Chomsky
Se han llamado lenguajes formales a aquellos que pueden ser generados por gramáticas formales. Chomsky estableció
que todos los lenguajes formales podían clasificarse en cuatro tipos (denominados lenguajes tipo 0, 1, 2 y 3) que solo
se distinguen por el formato de las producciones de las gramáticas que los generan. Mientras más restricciones se le
ponen a las producciones, en cuanto al formato de las cadenas de sus lados derecho e izquierdo, menos lenguajes
pueden describir, por lo que la clasificación es inclusiva.
Tipo 0: Lenguajes Estructurados por frases – Irrestrictos – Recursivamente Enumerables
Son los más generales en la jerarquía. Están descriptos por las reglas de reescritura menos restrictivas.
Las producciones pueden contener cualquier cadena de terminales y no terminales, tanto en el lado izquierdo como
en el lado derecho, con al menos un símbolo no terminal en el lado izquierdo. En símbolos:

Que también se puede escribir como:

Tipo 1: Lenguajes Dependientes del Contexto – Sensibles al Contexto

Permiten el reemplazo contextual de símbolos no terminales. Sus producciones tienen la forma:

El símbolo no terminal A solo puede ser reemplazado por la cadena 𝛾𝛾 de terminales y no terminales si se encuentra
flanqueada por α a la izquierda y β a la derecha, en el contexto alfa-beta.
Debe notarse que la cadena 𝛾𝛾 debe por lo menos tener largo unitario (pertenece a la cerradura positiva de la unión de
alfabetos de terminales y no terminales), por lo cual en estas reglas siempre la cadena del lado izquierdo es de largo
igual o menor que la cadena del lado derecho (reglas no compresoras); sin embargo, el lenguaje podría contener
como palabra a la cadena vacía, por lo cual ésta debe poder ser generada por la gramática. Por esto, se permite la
regla lambda 𝐒𝐒 ∶= 𝛌𝛌, como única regla compresora permitida.
Tipo 2: Lenguajes Independientes del Contexto – De contexto libre
La sintaxis de la gran mayoría de los lenguajes de programación se describe con gramáticas independientes del
contexto. Sus producciones pueden adoptar las siguientes formas:

El símbolo no terminal A, puede ser reemplazado por la cadena α de terminales y no terminales en cualquier lugar
donde aparezca durante el proceso de derivación, sin tener en cuenta el contexto donde se encuentra. Nótese que
estas reglas son también no compresoras, salvo la regla lambda que tiene idéntica justificación que en el tipo 1.
Tipo 3: Lenguajes Regulares o Lineales
Son los lenguajes que tienen producciones más restringidas dentro de la jerarquía de Chomsky.
Las producciones de las gramáticas que generan estos lenguajes tienen un solo símbolo no terminal del lado izquierdo
(como las tipo 2 anteriores), pero su lado derecho está compuesto por un solo símbolo terminal, o por un símbolo
terminal y un símbolo no terminal, aparte de poder tener la regla lambda.
Este formato de reglas de reescritura puede presentarse de dos formas, totalmente equivalentes:

Jerarquía Inclusiva
5. Lenguajes Regulares
Los lenguajes regulares admiten la siguiente definición recursiva:
a) Cualquier lenguaje finito (nro. natural de cadenas) L1 definido sobre algún alfabeto Σ, es regular.
b) Si L1 y L2 son lenguajes regulares, entonces también lo son su unión 𝐋𝐋𝟏𝟏 ∪ 𝐋𝐋𝟐𝟐 y su concatenación 𝐋𝐋𝟏𝟏 °𝐋𝐋𝟐𝟐
c) Si L1 es un lenguaje regular, entonces su estrella de Kleene L1* también es un lenguaje regular.
d) Sólo son lenguajes regulares los construidos con a), b) y c).
Expresiones Regulares

6. Lenguajes Independientes del Contexto (LIC)

Gramática Limpia
Se llama regla innecesaria a una regla del tipo A:=A en la que únicamente aparece a ambos lados del símbolo de
producción un mismo no terminal. Esta regla puede eliminarse del conjunto P de producciones de cualquier
gramática, sin ningún cambio adicional en la misma. Una regla innecesaria siempre puede detectarse por simple
inspección secuencial de los elementos del conjunto P.
Dado el caso de que alguno de los símbolos terminales o no terminales de la gramática, no pueda ser alcanzado
desde el axioma por ninguna derivación válida; esto significa que usando las producciones de la gramática y
partiendo desde el axioma, no hay manera de derivar una forma sentencial que lo contenga. Diremos en este caso que
el símbolo 𝑥𝑥 ∈ (ΣT ∪ ΣN ) es inaccesible. En símbolos:

Si esto ocurre, el símbolo x no intervendrá en la derivación de ninguna cadena del lenguaje generado por la
gramática, por lo que, si se lo quita, y junto con él todas las producciones que lo contengan, no se alterará el lenguaje
descripto.
Por otro lado, se sabe que el lenguaje formal generado por una gramática es un conjunto de cadenas de símbolos
terminales derivables desde el axioma; si existiera algún símbolo no terminal en la gramática desde el cual nunca se
pudiese llegar a una cadena de terminales utilizando producciones válidas, ese símbolo no terminal sería inútil. Se
denomina símbolo superfluo a un símbolo no terminal que no permite generar desde él al menos una cadena
vacía o de solo símbolos terminales:

Por esto, debe quitárselos del alfabeto respectivo y eliminar todas las producciones del conjunto P que los contengan,
obteniendo una nueva gramática equivalente a la anterior.
Se dice que una gramática independiente del contexto está limpia si y solo si no tiene reglas innecesarias, ni
símbolos inaccesibles, ni símbolos superfluos.
Gramática Bien Formada
El formato de las reglas de una GIC indica que no pueden existir reglas de reescritura compresoras, esto es,
producciones con lado derecho de menor longitud que el lado izquierdo.
En particular, una regla del tipo 𝐀𝐀: = 𝛌𝛌, no siendo A el axioma de la gramática, es una regla compresora denominada
regla no generativa. Si es el axioma el que produce la cadena vacía, 𝐒𝐒: = λ la regla se permite como excepción y ya
sabemos que se denomina regla lambda.
Si el lenguaje generado por la gramática contiene como elemento la cadena vacía, el lenguaje debe poder derivar
desde el axioma esta cadena, por lo cual una regla lambda no puede quitarse de una gramática sin modificar el
lenguaje generado. Sin embargo, sí resulta factible eliminar las reglas no generativas de una gramática.
Para poder quitar una regla no generativa 𝐀𝐀: = 𝛌𝛌, debe procederse de la siguiente forma:
a) Para cada producción 𝐗𝐗 ≔ 𝛂𝛂𝛂𝛂𝛂𝛂 que contenga el no terminal A en el lado derecho, agregar la regla de reescritura
𝐗𝐗 ≔ 𝛂𝛂𝛂𝛂 que se obtiene de reemplazar A por la cadena vacía.
b) Luego eliminar del conjunto de producciones 𝐀𝐀: = 𝛌𝛌.
Por otro lado:
Si tenemos producciones del tipo 𝐀𝐀: = 𝐁𝐁 donde A y B son símbolos no terminales; esta producción, llamada regla de
redenominación dice que el no terminal A puede ser reescrito como B en cualquier contexto donde se encuentre
Sin embargo, A puede tener otras reglas que indiquen reescritura (y así tener distintas definiciones del mismo símbolo)
y lo mismo puede ocurrir con B, pudiéndose generar sinonimia y polisemia simultáneamente. Además, el par de
producciones A:=B y B:=A podrían confundir a no pocas rutinas de análisis sintáctico que las analicen, generando
posibles lazos infinitos.
Para poder quitarlas (y poder determinar sin lugar a duda la sintaxis y semántica de nuestra gramática) debemos:
a) Por cada regla 𝐁𝐁 ≔ 𝛂𝛂 existente en la gramática, agregar una regla 𝐀𝐀 ≔ 𝛂𝛂, lo cual hace explícita como producción la
posible derivación en dos pasos 𝐀𝐀 → 𝐁𝐁 → 𝛂𝛂
b) Luego puede eliminarse 𝐀𝐀: = 𝐁𝐁 del conjunto de producciones y la gramática obtenida será equivalente a la original.
Se dice que una GIC está bien formada, si y solo si, está limpia y no tiene reglas no generativas ni de
redenominación.
7. Análisis Sintáctico - ¿ 𝛂𝛂 ∈ 𝐋𝐋(𝐆𝐆)?
Es el proceso de derivación el que permite obtener las cadenas del lenguaje L(G) descripto por la gramática y, en ese
sentido, decimos que la gramática genera el lenguaje.
En este sentido, nos interesa determinar si una cadena α dada de símbolos terminales, puede o no puede ser generada
por una gramática. En otras palabras, podemos preguntarnos si la cadena en cuestión está escrita de acuerdo con las
reglas de la gramática. Se concibe de tal manera que:

Se llama análisis sintáctico de la cadena α, al proceso de búsqueda de esta derivación.

Árbol de Derivación
Se necesitan entonces procedimientos claros y repetibles que, de manera sistemática, permitan responder si una
cadena pertenece o no, a un lenguaje independiente del contexto. En ese camino, se define una forma pictórica de
representar una derivación: el árbol de derivación o árbol de análisis sintáctico de la cadena.
Siempre debe iniciarse el proceso partiendo del axioma, aplicando al mismo una producción que lo tenga como lado
izquierdo.
Por tanto, una cadena α de símbolos terminales pertenece al lenguaje L(G) generado por la gramática G, si y solo si,
es posible construir su árbol de análisis sintáctico, con el axioma S como raíz y la cadena α leída en las hojas de
izquierda a derecha.
8. Ambigüedad
Cuando la misma cadena α de símbolos terminales, puede ser generada por distintas derivaciones que además
generan distintos árboles de derivación.
Se dice que una cadena es ambigua si puede ser generada por derivaciones que admiten distintos árboles de
análisis sintáctico.
Si una gramática permite esto también se dice que ella misma es ambigua y que genera su lenguaje en forma
ambigua. Sin embargo, en muchos casos, la gramática puede ser modificada o reescrita completamente para obtener
una gramática equivalente (que genera el mismo lenguaje) pero que no sea ambigua.
Existen algunos lenguajes independientes del contexto que solo pueden ser generados por gramáticas ambiguas. Se
los denomina lenguajes inherentemente ambiguos.
9. Recursión
una producción de una gramática independiente del contexto 𝐆𝐆 = (𝚺𝚺𝐓𝐓 , 𝚺𝚺𝐍𝐍 , 𝐒𝐒, 𝐏𝐏) se dice que es recursiva si el no
terminal de su lado izquierdo se encuentra también en el lado derecho:
𝐀𝐀: = 𝛂𝛂𝛂𝛂𝛂𝛂
donde 𝐀𝐀 ∈ 𝚺𝚺𝐍𝐍 es un símbolo no terminal de la gramática y α, β ∈ (𝚺𝚺𝐓𝐓 ∪ 𝚺𝚺𝐍𝐍 )∗ son cadenas de terminales y no terminales
de cualquier largo.
Una gramática que tiene una regla de reescritura recursiva, se dice que tiene recursión en un paso. En el caso en
el que un no terminal del lado izquierdo de una producción pueda derivarse en una cadena que lo contenga, en varios
pasos:

Si una gramática no tiene recursión (en un paso o en más de un paso), solo podrá generar un número finito de cadenas.

Si en la regla recursiva A:=αAβ la cadena α es vacía, esto es A:=Aβ se dice que la regla es recursiva por la izquierda
y que la gramática tiene recursión izquierda. Si en cambio es β la cadena vacía, esto es A:=αA, se dice que la regla es
recursiva por la derecha y que la gramática tiene recursión derecha.
Eliminación de recursión por izquierda en un paso

Eliminación de recursión por izquierda en más de un paso

10. Factorización por Izquierda

Se analiza el caso en que dos o más producciones inicien con una parte común:
A ≔ αβ y A ≔ αγ
donde α, β y γ son cadenas cualesquiera de terminales y no terminales. Esta situación se presta para confusión para
un analizador sintáctico. Sin embargo, si se crea un nuevo no terminal X y se reemplazan las anteriores producciones
por:
A ≔ αX y X ≔ β | γ
el procedimiento no tiene ahora dudas de lo que debe utilizar: la primera producción primero, y recién al terminar de
emparejar α con la cadena bajo análisis, deberá decidir con cuál de las producciones de X continúa el análisis de la
cadena bajo estudio.
11. Formas Normales de Gramáticas Independientes del Contexto
Las gramáticas independientes del contexto pueden ser expresadas en formas tales que, los lados derechos de sus
producciones estén restringidos a formatos normalizados. Es decir que el lado izquierdo debe seguir siendo solo un no
terminal, pero sus lados derechos estarán normados para obtener algunas características deseables.
Por tanto, se definen:
Forma Normal de Chomsky (FNC)
Una gramática se dice que está en Forma Normal de Chomsky si y solo si, todas sus producciones tienen en el
lado derecho dos símbolos no terminales, o un solo símbolo terminal o la cadena vacía (este último caso, solo
si el axioma se encuentra del lado izquierdo):
𝐀𝐀 ≔ 𝐁𝐁𝐁𝐁 𝐨𝐨 𝐀𝐀 ∶= 𝐚𝐚 𝐨𝐨 𝐒𝐒 ≔ 𝛌𝛌
donde 𝐀𝐀, 𝐁𝐁, 𝐂𝐂, 𝐒𝐒 ∈ 𝚺𝚺𝐍𝐍 son símbolos no terminales, S es el símbolo inicial de la gramática y 𝐚𝐚 ∈ 𝚺𝚺𝐓𝐓 representa un símbolo
no terminal. Una gramática en Forma Normal de Chomsky siempre tendrá árboles de derivación binarios.
Cualquier GIC podrá ser transformada en una equivalente en FNC mediante el siguiente procedimiento:

Forma Normal de Greibach (FNG)

Una gramática independiente del contexto está en Forma Normal de Greibach, si y solo si, todas sus producciones inician su
lado derecho con un símbolo terminal al que le sigue, opcionalmente, una cadena de símbolos no terminales de cualquier
largo. En símbolos, las producciones tienen una de las siguientes formas:
𝐀𝐀 ≔ 𝐚𝐚𝐚𝐚 𝐨𝐨 𝐒𝐒 ≔ 𝛌𝛌
con 𝐀𝐀, 𝐒𝐒 ∈ 𝚺𝚺𝐍𝐍 símbolos no terminales, S símbolo inicial de la gramática, 𝛈𝛈 ∈ 𝚺𝚺𝐍𝐍 ∗ cadena de símbolos no terminales de cualquier largo
y 𝐚𝐚 ∈ 𝚺𝚺𝐓𝐓 un símbolo no terminal. 𝛈𝛈 no puede ser vacía. Toda GIC puede ser reescrita para obtener una G equivalente en FNG:
 UNIDAD N°3 – Máquinas Secuenciales y Autómatas Finitos Deterministas
1. Máquinas Secuenciales
Para las máquinas abstractas o máquinas de estados más simples, se reserva la denominación de máquinas
secuenciales.
Máquina de Mealy
Tiene cinco componentes -quíntupla-, y se define como:
𝐌𝐌𝐌𝐌 = (𝚺𝚺𝐄𝐄 , 𝚺𝚺𝐬𝐬 , 𝐐𝐐, 𝐟𝐟, 𝐠𝐠)
Donde:
𝚺𝚺𝐄𝐄 → alfabeto de símbolos de entrada.
𝚺𝚺𝐒𝐒 → alfabeto de símbolos de salida.
𝐐𝐐 → conjunto finito y no vacío de estados posibles.
𝐟𝐟 → función de transición, 𝒇𝒇: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐐𝐐
𝐠𝐠 → función de salida, 𝒈𝒈: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝚺𝚺𝐒𝐒
La función de transición f define el próximo estado que adoptará la máquina a partir de su estado actual y cada
uno de los posibles símbolos de entrada.
La función de salida g define la salida de la máquina con los mismos argumentos.
Se pueden representar tanto por medio de tablas como por medio de dígrafos.
La máquina de Mealy –ME en adelante– es una traductora, e.d, establece una relación entre una cadena de entrada
y una de salida.

Máquina de Moore
Tiene los mismos cinco componentes ya indicados para la máquina de Mealy, diferenciándose únicamente en su
función de salida, puesto que sólo depende del estado actual y no de la entrada en ese instante. Es decir:
𝐌𝐌𝐌𝐌 = (𝚺𝚺𝐄𝐄 , 𝚺𝚺𝐬𝐬 , 𝐐𝐐, 𝐟𝐟, 𝐠𝐠)
donde la función de transición f no cambia y en g hay una relación directa entre el estado en cada intervalo de
tiempo y el símbolo de salida.
𝒇𝒇: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐐𝐐 𝒈𝒈: 𝐐𝐐 → 𝚺𝚺𝐒𝐒
La MO incorpora un retardo entre la entrada y la salida. Si en un instante t el autómata se encuentra en un estado
𝐪𝐪𝐭𝐭 ∈ 𝐐𝐐 la salida será:
st = g(qt )
y como éste estado fue a su vez alcanzado en una transición anterior:
qt = f(qt−1 , et−1 )
se puede apreciar la relación directa entre la salida actual y la entrada en un instante anterior, que es:
st = g(f(qt−1 , et−1 ))
Para toda máquina de Moore hay una máquina de Mealy capaz de tener el mismo desempeño y recíprocamente.
2. Autómatas Finitos Deterministas
2.1 Definición del AFD
Si a la ME se le incorpora un estado inicial y un conjunto de estados de aceptación, estamos en presencia de un
Autómata Finito Determinista (AFD). En su forma más general, el AFD es una séptupla, comienza a operar a partir
de un estado inicial, tiene una conducta traductora ya que transforma las cadenas de entrada en cadenas de salida y
completa su operación al terminar de leer su entrada, arribando a un estado que podrá ser de aceptación o no. E.d:
𝐀𝐀𝐀𝐀𝐀𝐀𝐓𝐓 = (𝚺𝚺𝐄𝐄 , 𝚺𝚺𝐬𝐬 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟, 𝐠𝐠)
Donde:
𝚺𝚺𝐄𝐄 → alfabeto de símbolos de entrada.
𝚺𝚺𝐒𝐒 → alfabeto de símbolos de salida.
𝐐𝐐 → conjunto finito y no vacío de estados posibles.
𝐪𝐪𝐨𝐨 → estado inicial de operación, q0 ∈ Q
𝐀𝐀 → conjunto de estados de aceptación, A ⊆ Q
𝐟𝐟 → función de transición, 𝒇𝒇: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐐𝐐
𝐠𝐠 → función de salida, 𝒈𝒈: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝚺𝚺𝐒𝐒
Por tener un estado inicial y ser la cadena de entrada finita, el AFDT siempre completa su operación, de la misma
forma, en una cantidad finita de tiempo y, por lo tanto, determina un algoritmo.
Si se limita únicamente a reconocer o validar cadenas, resultan innecesarios el alfabeto de salida y su función de salida,
por lo que ambas se eliminan y se obtiene un Autómata Finito Reconocedor 𝐀𝐀𝐀𝐀𝐀𝐀𝐑𝐑 que queda definido como una
quíntupla. En adelante nos referiremos al AFDR como AFD:
𝐀𝐀𝐀𝐀𝐀𝐀𝐑𝐑 = (𝚺𝚺𝐄𝐄 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟)
Comienza a operar a partir del estado inicial 𝐪𝐪𝟎𝟎 y, al completar la lectura de la cadena de entrada, confirma su
aceptación arribando a uno de los estados del conjunto A de estados de aceptación.
Un caso particular de aceptación ocurre cuando la cadena de entrada es la palabra vacía 𝛌𝛌: el AFD la aceptará si su
estado inicial es también un estado de aceptación: 𝐪𝐪𝟎𝟎 ∈ 𝐀𝐀.
El hecho de tener el componente f definido como función es lo que lleva a definir al autómata como determinista.
Esta puede ser total o parcial, y cuando el autómata llega a condiciones en las que no tiene definido el próximo estado,
se detiene (razón por la cual se añade generalmente un estado de error).
A partir de una cierta cadena de entrada 𝛂𝛂, en cada intervalo de tiempo, se conoce tanto el prefijo ya leído por el AFD
como también el sufijo que representa la cadena que resta ser leída. Luego, cuando la cadena ya fue leída
completamente el prefijo leído es igual a 𝛂𝛂 y el sufijo a ser leído es igual a 𝛌𝛌, lo que significa que no hay nada por leer.
La máquina se puede parar por las siguientes razones:
i) la función de transición es parcial, no estando definido un próximo estado (la cadena es, por lo tanto, rechazada).
ii) se completó la lectura de la cadena de entrada.
a) se encuentra en un estado de aceptación (𝐪𝐪 ∈ 𝐀𝐀) y, por eso, la cadena es aceptada o reconocida,
b) se encuentra en cualquier otro estado (𝐪𝐪 ∉ 𝐀𝐀) lo que indica que la cadena es desconocida o rechazada.
Por lo expuesto, se admite en lo sucesivo que todo estado 𝐪𝐪 ∈ 𝐀𝐀 es un estado de aceptación (se dibujará con doble
círculo en el dígrafo) y todo estado 𝐩𝐩 ∈ (𝐐𝐐 − 𝐀𝐀) es un estado de no aceptación o rechazo.
2.2 Configuración o Descripción Instantánea
Se define como configuración o descripción instantánea 𝐊𝐊 𝐭𝐭 de un autómata finito en un intervalo de tiempo t al par
ordenado:
𝐊𝐊 𝐭𝐭 = (𝐪𝐪, 𝛃𝛃) 𝐜𝐜𝐜𝐜𝐜𝐜 𝐪𝐪 ∈ 𝐐𝐐, 𝛃𝛃 ∈ 𝚺𝚺𝐄𝐄 ∗

donde q representa el estado en el que se encuentra y 𝛃𝛃 el sufijo o subcadena de entrada que está pendiente de ser leída.
Con una cadena 𝛂𝛂 de entrada a ser procesada, se reconoce a la configuración inicial como
𝐊𝐊 𝟎𝟎 = (𝐪𝐪𝟎𝟎 , 𝛂𝛂)
A la configuración de aceptación como:
𝐊𝐊 𝐧𝐧 = (𝐪𝐪𝐧𝐧 , 𝛌𝛌) 𝐝𝐝𝐝𝐝𝐝𝐝𝐝𝐝𝐝𝐝 𝐪𝐪𝐧𝐧 ∈ 𝐀𝐀, 𝐧𝐧 = |𝛂𝛂|
El tránsito de una configuración a otra se denomina movimiento; si existe la transición q=f(p,a) el movimiento del
estado p a q leyendo a, puede representarse como:

El comportamiento del autómata ante cierta cadena de entrada queda representado por un árbol de configuraciones o
de descripciones instantáneas, y como alt. puede utilizarse un esquema denominado plano de estados–entradas.
2.3 Extensión al tratamiento de palabras

2.4 Aceptación de Cadenas y otros conceptos asociados a los AFD

Aceptación de Palabras y Lenguajes
Si en el movimiento desde la configuración inicial hasta la final, rep. como (𝒒𝒒𝟎𝟎 , 𝜶𝜶) ⊢∗ (𝒒𝒒𝒏𝒏 , 𝝀𝝀) se verifica que 𝐪𝐪𝐧𝐧 ∈ 𝐀𝐀.
La aceptación de una cadena por parte de un AFD implica dos condiciones simultáneas:
i) la completa lectura de la cadena de entrada α y
ii) el arribo a un estado de aceptación. Por el contrario, si 𝐪𝐪𝐧𝐧 ∉ 𝐀𝐀 la cadena α habrá sido rechazada.
A partir de lo anterior, un lenguaje L es aceptado por un autómata finito M si todas las palabras que lo componen
conducen el autómata a símbolos de aceptación. Simbólicamente:

Accesibilidad entre estados

En un AFD, se dice que un estado p es accesible desde otro estado q, y se representa pAq, si existe una palabra de
símbolos de entrada que haga transitar el autómata desde el estado q hasta el estado p. En símbolos:

Nótese que todos los estados inaccesibles desde el estado inicial q0 pueden ser eliminados de un autómata finito ya
que no afectan su comportamiento, en cuanto a reconocimiento de cadenas se refiere.
Autómatas Conexos
Si todos los estados de un autómata son accesibles desde su estado inicial se dice que el mismo es conexo. En
símbolos:
2.5 Equivalencia de Estados y Autómatas
Equivalencia entre estados
Dos estados p,q ∈ Q de un AFD se dice que son equivalentes, lo que es representado por pEq, si desde cualquiera
de ellos se aceptan y rechazan exactamente las mismas cadenas de símbolos de entrada.

Se reconoce entonces que entre dos elementos p y q del conjunto de estados posibles Q, se ha establecido una relación
de equivalencia E, que satisface las propiedades reflexiva, simétrica y transitiva en Q.
Nótese que, según la relación de equivalencia presentada, es imposible distinguir entre dos estados equivalentes, lo
que lleva a denominarlos indistinguibles. Además, si los estados p y q son equivalentes y |A|>1, puede ocurrir que los
estados de aceptación o rechazo alcanzables a partir de cierta cadena α, no sean necesariamente los mismos.
Equivalencia de longitud “k” entre estados
Dos estados p, q ∈ Q de un AFD son equivalentes de longitud k, lo que se representa con pEkq, si son equivalentes
para todas las cadenas de largo menor o igual a k. Esto puede expresarse en símbolos:

Equivalencia entre autómatas

Dos AFD denominados A1 y A2, se dice que son equivalentes y se representa A1EA2, si ambos aceptan las mismas
palabras o sentencias. De aquí se deduce que dos AFD son equivalentes si lo son sus estados iniciales. Lo
anterior implica que dos AFD son equivalentes si y solo si aceptan el mismo lenguaje. En símbolos:

Conjunto Cociente
La relación E definida sobre el conjunto de estados posibles Q, induce en el mismo una partición. Todos los elementos
de Q relacionados con cierto estado p∈Q, constituyen un subconjunto de Q que es denominado clase de equivalencia
de p.
Se denomina conjunto cociente a esa partición, conjunto que tiene por elementos a todas las clases de
equivalencia o subconjuntos de estados equivalentes entre sí que puedan distinguirse en el conjunto de
estados Q. Por ser la base de este agrupamiento, la relación de equivalencia entre estados E, el conjunto cociente se
denota Q/E.

Se recurre a un procedimiento práctico incremental que comienza con un particionamiento o conjunto cociente inicial de Q, que es
sucesivamente revisado con cadenas progresivamente más largas, a partir de k=1 y hasta que las clases de equivalencia de Q se
estabilicen en cantidad y contenido, no sufriendo cambios para cadenas de mayor longitud.
2.6 Minimización de Autómatas
El concepto de autómata mínimo se define como aquel que cumple correctamente su función con la menor
cantidad posible de estados.
Todo autómata que sea conexo y opere correctamente con más estados de los necesarios debe tener en su definición
estados equivalentes o indistinguibles.
Esto significa que tal autómata debe ser minimizado y para ello se recurre al concepto de conjunto cociente, es
decir, a la partición del conjunto de estados Q producida por la relación de equivalencia E, que tiene por elementos a
las clases de equivalencia, donde se agrupan todos los estados equivalentes o indistinguibles entre sí.
El autómata mínimo equivalente a uno dado, tendrá como estados a cada una de las partes o clases de estados
equivalentes del autómata original (es decir, su conjunto de estados será Q/E), aquella clase que contenga el
estado inicial original será su estado inicial, las que contengan algún estado de aceptación del autómata original serán
sus estados de aceptación; su función de transición se construirá en base a la del autómata original.

3. Autómatas Finitos Bidireccionales

3.1. Aspectos Generales
Los autómatas finitos leen siempre la cadena de entrada de izquierda a derecha. Esto tiene varias consecuencias:
1. cada símbolo de la cadena es leído una única vez.
2. al completarse la lectura, la cadena es aceptada o no, según se alcance un estado de aceptación.
3. puede anticiparse la cantidad de intervalos de tiempo necesarios para evaluar la cadena, que será igual a su largo.
4. en todo momento está claramente definida la subcadena pendiente de ser leída por el autómata, soportando el
concepto de configuración o descripción instantánea del AFD.
Otorgando a un AFD la capacidad de decidir el sentido del movimiento del cabezal en cada intervalo de tiempo
queda conceptualmente definido el AFDB (Autómata Finito Determinista Bidireccional). Por ello:
• Se debe incorporar una función de movimiento, que defina el sentido del movimiento del cabezal en cada estado
y ante cada símbolo de entrada.
• Debe quedar claramente establecido el sector de la cinta en el que el autómata puede operar. Para ello, se
incorporan dos símbolos especiales que identifican el inicio y el final del intervalo de cinta de entrada a ser
analizado.
Con esto, se obtiene un autómata que cambia las condiciones antes señaladas, a saber:
1. Cada símbolo de entrada puede ser leído varias veces.
2. No hay ninguna condición que indique el fin de la lectura de la cadena,
3. No es posible anticipar la cantidad de intervalos de tiempo requeridos para evaluar la cadena.
4. El concepto de cadena que resta de ser leída desaparece.
Se suma aquí una consecuencia novedosa, que es la real posibilidad de que ciertas cadenas de entrada lleven al AFDB
a un ciclo cerrado que no conduzca a nada, es decir, un ciclo infinito.
A partir de lo anterior, el AFDB se define como:
𝐀𝐀𝐀𝐀𝐀𝐀𝐀𝐀 = (𝚺𝚺𝐄𝐄 , 𝚪𝚪, 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟)
𝚺𝚺𝐄𝐄 → alfabeto de símbolos de entrada.
𝚪𝚪 → alfabeto de cinta, Γ = ΣE ∪ {⊢, ⊣}
𝐐𝐐 → conjunto finito no vacío de estados posibles
𝐪𝐪𝟎𝟎 → estado inicial de operación, q0 ∈ Q
𝐀𝐀 → conjunto de estados de aceptación, A ⊆ Q
𝐟𝐟 → función de transición, 𝑓𝑓: Q x Γ → Q x {I, N, D}
 3.2. Conceptos Asociados a los AFDB
Aceptación de Cadenas
Una cadena es aceptada por el AFDB cuando éste ha alcanzado un estado de aceptación y la cadena ha sido leída
por lo menos una vez. Esto último significa que la cantidad de intervalos de tiempo demandados por la aceptación
será igual o mayor al largo de la cadena en cinta. Nótese que si la cantidad de intervalos de tiempo necesarios para
aceptar una cadena es igual a su largo, el AFDB se ha comportado como un AFD convencional.
Configuración
Para la completa definición de la condición en la que se encuentra un AFDB en un instante dado se requieren tres
componentes, que son: el estado actual, el contenido de la cinta de entrada y la posición del cabezal.
Para esto último, se adopta la convención de que el símbolo de inicio de cinta (BOT) está en la posición 0 y el contador
se incrementa hacia la derecha, lo que implica que el primer carácter de la cadena de entrada está en la posición 1.

Lenguaje reconocido por el AFDB

Usando a la notación de movimientos entre configuraciones definida para los autómatas finitos, el lenguaje L que es
aceptado por un autómata finito bidireccional M puede definirse en símbolos como:

El problema de la parada
Ya fue anticipado que el AFDB puede quedar atrapado en un ciclo cerrado Siendo finitos el conjunto de estados posibles y la
cinta de entrada, aunque con cierto esfuerzo, esta situación puede determinarse entonces por un algoritmo.
Extensión al tratamiento de palabras
Es realizada al igual que en el AFD. Aunque no la explicitaremos aquí, es importante notar que en este caso la extensión debe
incluir también la función de movimiento, ya que esta última es determinante en el comportamiento del AFDB.
Equivalencia entre AFDB y AFD
El movimiento del cabezal en dos sentidos no brinda ninguna capacidad adicional con respecto al AFD, lo que implica que todo
AFDB tiene un AFD equivalente, lo que aquí no es demostrado. El razonamiento inverso ya fue establecido al admitirse que los
AFD son un caso particular del AFDB.
 UNIDAD N°4 – Autómatas Finitos No Deterministas
1. No determinismo y Autómatas
La primera forma de no determinismo se manifiesta con la presencia de múltiples opciones posibles en la función
de transición. Los AFND quedan determinados como una quíntupla:
𝐀𝐀𝐀𝐀𝐀𝐀𝐀𝐀 = (𝚺𝚺𝐄𝐄 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟)
donde su característica distintiva subyace en la definición de las transiciones, que aquí es una relación de
transición, tomando la forma:
𝒇𝒇: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐏𝐏(𝐐𝐐)
donde P(Q) es el conjunto de todos los subconjuntos que se pueden formar con elementos del conjunto Q
(conjunto potencia de Q). Nótese que aquí la indeterminación implica incertidumbre en cuanto al esfuerzo requerido al
evaluar una cierta cadena. La cantidad de intervalos de tiempo t que le insume a un AFND aceptar o rechazar una
cadena es compleja de acotar, porque la operación del autómata implica una búsqueda exhaustiva en un árbol de
posibilidades, que será más frondoso según sea mayor la cantidad de próximos estados posibles en cada transición.
A lo anterior se lo llama factor de ramificación FR donde 𝐅𝐅𝐑𝐑 = |𝒇𝒇(𝒒𝒒, 𝒆𝒆)|, 𝒒𝒒 ∈ 𝑸𝑸, 𝒆𝒆 ∈ 𝚺𝚺𝐄𝐄 ; crecimiento exponencial.
Finalidad de los AFND → la flexibilidad que ofrece el no determinismo es de gran ayuda en el diseño de autómatas
destinados a reconocer lenguajes complejos.
2. Autómatas Finitos No Deterministas
Acorde a lo anterior, el no determinismo es un recurso conveniente para definir máquinas abstractas.
2.1 Transiciones Lambda
La definición de los AFND puede ampliarse para incluir transiciones de un estado a otro que no dependan de
ninguna entrada, denominadas transiciones λ. Con el símbolo λ, se representa la cadena vacía (|𝛌𝛌| = 𝟎𝟎). Estos
autómatas se llamarán AFND-λ.
Cualquier descripción instantánea de esta máquina se considera de la misma forma que si se tratara de una
transición convencional ante una cierta entrada 𝒆𝒆 ∈ 𝚺𝚺𝐄𝐄 .
Por ello, se incorpora una nueva columna adicional a la relación f a fin de considerar los pares (𝒒𝒒, 𝝀𝝀), asumiendo
que cada estado tiene su propia transición 𝛌𝛌. La expresión f se reescribe como:
𝒇𝒇: 𝐐𝐐 𝐱𝐱 (𝚺𝚺𝐄𝐄 ∪ {𝝀𝝀}) → 𝐏𝐏(𝐐𝐐)
A todos los pares de estados vinculados por una transición 𝝀𝝀 es conveniente reunirlos en el conjunto T denominado
relación de transición 𝝀𝝀. Se incluyen, además, las transiciones de los estados con ellos mismos (reconociendo el
carácter reflexivo de T). En símbolos:
𝐓𝐓 = {(𝐩𝐩, 𝐪𝐪)/𝐪𝐪 ∈ 𝐟𝐟(𝐩𝐩, 𝛌𝛌)} ∪ {(𝐪𝐪, 𝐪𝐪)/𝐪𝐪 ∈ 𝐐𝐐}
que, utilizando notación de relaciones, queda:

Luego se incorporan al conjunto T nuevos pares ordenados, que se originan en la aplicación de la propiedad
transitiva a los pares anteriores. Se obtiene así el cierre transitivo de la relación, de la forma:
𝐓𝐓 ∗ = 𝐓𝐓 ∪ {(𝐩𝐩, 𝐪𝐪)/𝐩𝐩𝐩𝐩𝐩𝐩 ∧ 𝐫𝐫𝐫𝐫𝐫𝐫}
2.2 Extensión al tratamiento de palabras
La relación de transición 𝒇𝒇 define los estados alcanzables a partir de cada uno de los estados y para cada uno de
los símbolos del alfabeto de entrada. Esta relación puede ser extendida para describir lo que ocurre a partir de cada
estado si en lugar de recibir símbolos aislados se recibe una secuencia concatenada de los mismos. La noción de
relación de transición extendida 𝒇𝒇𝒆𝒆 para reconocer cadenas o palabras puede inducirse a partir de un razonamiento
similar al hecho cuando se definió la función de transición extendida para el AFD, considerando además la eventualidad
de las transiciones 𝛌𝛌. Se obtiene una relación que queda definida como:

2.3 Equivalencia con Autómatas Finitos Deterministas

Teorema 1
Todo AFND-λ puede ser redefinido como un AFND equivalente, para lo cual se deben eliminar sus transiciones λ.
Enunciado → sea un AFND-λ que es definido como 𝐌𝐌 = (𝚺𝚺𝐄𝐄 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟) donde
𝒇𝒇: 𝐐𝐐 𝐱𝐱 (𝚺𝚺𝐄𝐄 ∪ {𝝀𝝀}) → 𝐏𝐏(𝐐𝐐)
Este autómata puede ser siempre redefinido en como un AFND en el que 𝐌𝐌′ = (𝚺𝚺𝐄𝐄 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀′, 𝐟𝐟′) donde 𝒇𝒇′: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐏𝐏(𝐐𝐐)
Procedimiento de aplicación:
Nótese que A=A’, ya que las
transiciones definidas en (b)
mantienen el mismo conjunto de
estados de aceptación, siempre
que no se presente el caso
definido en (c).

Teorema 2
Por cada AFND, siempre existe un AFD que acepta el mismo lenguaje, y estos dos autómatas son equivalentes.
Enunciado → sea un AFND definido como 𝐌𝐌 = (𝚺𝚺𝐄𝐄 , 𝐐𝐐, 𝐪𝐪𝟎𝟎 , 𝐀𝐀, 𝐟𝐟) donde
𝒇𝒇: 𝐐𝐐 𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐏𝐏(𝐐𝐐)
Siempre existirá un AFD 𝐌𝐌′ = (𝚺𝚺𝐄𝐄 , 𝐐𝐐′, 𝐜𝐜𝟎𝟎 , 𝐀𝐀′, 𝐟𝐟′) con 𝒇𝒇′: 𝐐𝐐 ′𝐱𝐱 𝚺𝚺𝐄𝐄 → 𝐐𝐐′ que es equivalente.
Caso 1 – AFND en el que ya han sido eliminadas sus transiciones λ

Caso 2 – AFND-λ – no han sido previamente eliminadas las transiciones λ

Debe notarse que, cualquiera sea el procedimiento empleado, es muy probable que el AFD equivalente no sea
conexo e incluya estados indistinguibles, por lo que deba ser minimizado.
3. Gramáticas Regulares y Autómatas Finitos
3.1 Definición de gramáticas regulares a partir de autómatas
Se comienza por el caso en que se quiere definir el conjunto de reglas de producción de una gramática regular
que generará lenguajes que están destinados a ser reconocidos por un cierto AFD. Para ello, el AF debe ser
determinista y la gramática a ser obtenida estará bien formada y será lineal por derecha.

3.2 Definición de autómatas a partir de gramáticas regulares

Se conoce cierta gramática y se desea determinar el AFD que será necesario para reconocer o validar las
sentencias del lenguaje generado. Como en el caso anterior, el procedimiento propuesto se refiere a gramáticas
bien formadas y cuyas reglas de producción sean lineales por derecha.

Deben considerarse que:

1. La existencia en la gramática de una regla de producción S:= λ convierte al autómata asociado en AFND-λ
2. Para el caso de que la gramática sea lineal por izquierda será necesario convertirla previamente a lineal por
derecha, aplicando el procedimiento que es definido a continuación.
3.3 Conversión de gramática lineal por izquierda a lineal por derecha
Para cada gramática lineal por derecha, existe una gramática lineal por izquierda equivalente y viceversa; como se
recordará, dos gramáticas son equivalentes si generan el mismo lenguaje. Los pasos por seguir son:
4. Expresiones Regulares y Autómatas Finitos
Se destacan los teoremas de análisis y de síntesis, con los cuales se establece y demuestra que un lenguaje es
regular si y solo si es aceptado por un autómata finito. Para ello, Kleene desarrolló la operación estrella ya
estudiada y la notación que llamamos expresiones regulares.
4.1 Método o Algoritmo de Thomson
Traduce cada parte de la definición de una expresión regular en un autómata que acepta el mismo lenguaje
denotado por ella, de tal forma que el autómata finito quede definido al analizar la expresión parte por parte.
Recordemos que la definición de una expresión regular tiene una parte básica (∅, 𝝀𝝀, 𝒂𝒂 siendo 𝒂𝒂 cualquier símbolo
del alfabeto) y una parte recursiva (𝐄𝐄 + 𝐅𝐅, 𝐄𝐄°𝐅𝐅, 𝐄𝐄 ∗ , (𝐄𝐄), siendo E y F expresiones regulares).
En los siguientes puntos, se trabajará siempre suponiendo que las expresiones regulares están describiendo un
lenguaje sobre algún alfabeto Σ y se construirá un autómata finito AF AF = (ΣE , Q, q0 , A, 𝑓𝑓)mostrando su grafo dirigido.
a) Para que la expresión regular ∅ que denota al lenguaje vacío se construye un AF que reconozca este lenguaje.
Esto puede hacerse de dos formas equivalentes: construyendo un autómata que tenga el
conjunto A de estados de aceptación vacío, o que tenga un único estado de aceptación
aislado; se procede de la segunda forma:
b) La expresión regular 𝛌𝛌 denota al lenguaje cuya única cadena es la vacía. Tenemos
dos modos de construir el AF: haciendo que su estado inicial sea a la vez de aceptación, o
equivalentemente con una transición 𝛌𝛌 como único acceso a un estado de aceptación desde
su estado inicial:
c) Para cada símbolo 𝒂𝒂 ∈ 𝚺𝚺, la expresión regular a denota al lenguaje {a}, y el autómata
finito correspondiente es el mostrado en la siguiente figura

El autómata finito no determinista construido de esta forma conecta en paralelo los autómatas ya existentes para E y
F utilizando transiciones 𝛌𝛌, logrando aceptar todas las cadenas que ambos aceptaban, es decir, la unión de sus
lenguajes.

Cualquier cadena que tenga un prefijo descripto por E, hará que el nuevo AF transite desde su estado inicial hasta
alguno de los antiguos estados finales de AFE y desde allí espontáneamente hasta el antiguo estado inicial de AFF (por
la transición 𝛌𝛌); si la cadena tiene luego un sufijo que sigue el patrón F, entonces hará que el autómata arribe a alguno
de los antiguos estados de aceptación de AFF y desde allí pueda pasar sin leer entradas hasta el nuevo estado de
aceptación qA. Esto acepta entonces, cadenas que sigan el patrón EF.
El método de Thompson termina construyendo un AFND- λ con muchos estados, por lo cual debe ser luego
transformado en determinista (y posiblemente minimizado) para su implementación eficiente en programación, pero su
importancia radica en que es un procedimiento automático que puede ser programado (es lo que hace el generador de
analizadores léxicos lex de UNIX).
 UNIDAD N°5 – AUTÓMATA CON PILA
Definición
El AP es un autómata finito al que le fue incorporado una memoria LIFO. La memoria de pila o memoria
LIFO (Last In First Out) incrementa la capacidad de resolver problemas del autómata finito
convencional, al incorporarle la posibilidad de memorizar total o parcialmente la cadena leída y cualquier
otra marca que ayude al procesamiento de la misma.
Un autómata con pila es una máquina abstracta compuesta por una séptupla:
AP = (ΣE, Γ, Q, q0 , #, A, f )
cuyos componentes son:
- ΣE: alfabeto de símbolos de entrada
- Γ: alfabeto de símbolos de pila
- Q: conjunto finito y no vacío de estados posibles
- q0∈Q: estado inicial de operaciones del autómata
- # ∈ Γ ∧ # ∉ Σ: símbolo de pila vacía o de fondo de pila
- A⊆Q: conjunto de estados de aceptación
- f : Q × (ΣE ∪ {λ}) × Γ → P(Q × Γ*) función de transición
Funcionamiento
Iniciando el funcionamiento en el estado inicial q0, y con la pila vacía marcada por #, el autómata:
1. Lee un símbolo de entrada lec=eleido o no lee lec=λ.
2. Saca un símbolo de pila w=sacar().
3. Transita a uno o más estados y almacena cadenas en la pila { (q1 ,β1 ), (q2 ,β2 ), …, (qm,βm) } = f(qactual,
lec, w).
4. Repite los pasos 1-3 en forma no determinística hasta terminar de leer la cadena de entrada.
5. Decide si acepta o rechaza la cadena leída.
Aquí el funcionamiento es no determinista de varias formas:
a) El AP puede leer un símbolo de entrada o no leer, por lo que puede realizar transiciones espontáneas (λ).
b) El rango de la función de transición es P(Q × Γ*), por lo que puede transitar a varios estados y por cada
estado:
c) Podría realizar sobre la pila una de varias acciones:
1. Desapilar: extrae un símbolo y no almacena nada.
2. Apilar: extrae un símbolo y lo devuelve con algo más.
3. Cambiar: extrae un símbolo y almacena algo más.
Acciones posibles sobre la pila durante una transición desde el estado p al estado q, al leer el símbolo a de
la entrada y estando el símbolo w en la cima de la pila:
1. Desapilar: extrae un símbolo w y no almacena nada.
f(p, a, w) = { (q, λ) } no graba nada
2. Apilar: extrae un símbolo w y lo devuelve con algo más wβ.
f(p, a, w) = { (q, wβ) } con β∈Γ+
3. Cambiar: extrae un símbolo w y almacena algo más β.
f(p, a, w) = { (q, β) } con β∈Γ+
Autómata con Pila Determinista
Si bien el autómata con pila definido es claramente no determinista, puede restringirse la función de
transición de tal forma que el APND se comporte como un APD. Se proponen dos formas de hacer esto:
a) Quitar las transiciones espontáneas y el conjunto potencia:
f : Q × ΣE × Γ → Q × Γ*
b) Permitir las transiciones espontáneas en forma restringida y quitar el conjunto potencia:
f : Q × (ΣE ∪ {λ}) × Γ → Q × Γ*
con la condición de que si |f(q, λ, w) = 1| está definida no lo esté f(q, a, w) para ningún s.d.e a.
Representación
Al tener la función de transición de los APD y APND tres argumentos, se imposibilita la representación
mediante tabla. Para casos en los que las cantidades de Q y Γ es poco numerosa, se puede realizar dicha
tabla.
La representación más común es mediante un grafo, cuyos arcos dirigidos están rotulados con una etiqueta
a,b/α donde α ∈ ΣE a, b / α, donde a∈ΣE representa el símbolo de entrada leído, b∈Γ el símbolo leído del
tope de pila y α∈Γ* representa la cadena grabada sobre la pila.
Configuración o Descripción Instantánea
Kt = (q, α, β)
q=estado actual, α=cadena que resta de ser leída, β=contenido de la pila
Configuración Inicial:
K0 = (q0 , α, #)
q0=estado inicial, α=cadena a procesar, #=símbolo de pila vacía
Configuración final:
Kf = (qf , λ, δ)
qf=estado final, λ=no queda cadena por leer, δ=contenido de la pila
Movimiento: Al igual que en los AF, se denomina movimiento al tránsito de una configuración a otra en un
paso:
(q, aα, wβ) Ͱ (p, α, wβx)
Solo posible si f(q, a, w) = { (p, x) }
Movimiento generalizado: Tránsito de una configuración a otra en uno o más pasos:
(q, α, β) Ͱ* (p, µ, δ)
Significa: (q, α, β) Ͱ (q1 , α1 , β1 ) Ͱ (q2 , α2 , β2 ) Ͱ … Ͱ (p, µ, δ)
El árbol de configuraciones de una cadena, muestra adecuadamente el proceso que el AP realiza sobre la
misma.
Los APD y APND no son necesariamente equivalentes; un APND no tiene necesariamente un APD
equivalente que acepte los mismos lenguajes. El no determinismo otorga a los APND mayor poder de
cómputo respecto de los APD. Esto quiere decir que un APND puede reconocer lenguajes que un APD
no puede.
Aceptación de Cadenas
Para los autómatas con pila, pueden definirse tres formas de aceptación o reconocimiento de cadenas:
1. Aceptación por vaciado de pila: al terminar de leer la cadena de entrada, la pila queda vacía, en
cualquier estado. (q0 , α, #) Ͱ* (qf , λ, #), con q0 ,qf∈Q, α∈Σ* , #∈Γ
2. Aceptación por estado de aceptación: al terminar de leer la cadena de entrada, se llega a un estado de
aceptación. (q0 , α, #) Ͱ* (qf , λ, δ), con q0∈Q, qf∈A, α∈Σ* , δ∈Γ*
3. Aceptación por ambos criterios simultáneamente:
(q0 , α, #) Ͱ* (qf , λ, #), con q0∈Q, qf∈A, α∈Σ* , #∈Γ
Lenguaje reconocido por un AP
Las tres formas de aceptación o reconocimiento de cadenas dan tres formas de reconocer un lenguaje:
1. Reconocimiento por vaciado de pila:
L(AP) = {α∈Σ* / (q0 , α, #) Ͱ* (qf , λ, #), con q0 ,qf∈Q, #∈Γ }
2. Reconocimiento por estado de aceptación:
L(AP) = {α∈Σ* / (q0 , α, #) Ͱ*(qf , λ, δ), con q0∈Q, qf∈A, δ∈Γ* }
3. Reconocimiento por ambos criterios simultáneamente:
L(AP) = {α∈Σ* / (q0 , α, #) Ͱ* (qf , λ, #), con q0∈Q, qf∈A, #∈Γ }
Autómatas con Pila Asociados a una Gramática
Isomorfismo entre AP y GIC
Dada una gramática independiente del contexto (GIC): G = (ΣT , ΣN , S, P) el problema de análisis sintáctico
es determinar si una cadena α de símbolos terminales puede ser generada por la gramática: ¿α∈L(GIC)?
Esta pregunta tiene una respuesta afirmativa SI, si puede construirse una derivación S→*α de la cadena α
partiendo desde el axioma S, usando las producciones en P. Otra forma de responderla es construir el árbol
de análisis sintáctico para α.
Hay al menos dos formas generales de construir un autómata con pila, para que durante su
funcionamiento al procesar una cadena de entrada, construya la derivación o el árbol de análisis sintáctico
de la misma.
• Enfoque Descendente: partir desde el axioma S e identificar las producciones de la gramática que
sucesivamente deben aplicarse para construir una derivación por la izquierda de la cadena mientras se
consume la misma. Genera el árbol desde la raíz hacia las hojas.
• Enfoque Ascendente: se parte desde la cadena de entrada y se identifican las reducciones a realizar
para construir una derivación por la derecha de atrás hacia adelante. Genera el árbol desde las hojas
hacia la raíz.
Compiladores y AP
Se emplean en la primera etapa del compilador, llamada etapa de análisis. Particularmente, se emplean
para construir analizadores sintácticos, utilizados en la fase de análisis sintáctico. Pueden agruparse en
descendentes y ascendentes.
Se distinguen familias de analizadores que responden a diferentes criterios, entre ellos las formas normales
en las que deben estar expresadas las producciones de las gramáticas. El determinismo de los analizadores
y la utilización de procedimientos recursivos, son otros criterios de clasificación.
Analizadores Sintácticos Descendentes
El Analizador Sintáctico Descendente (ASD), en inglés Top-Down Parser, comienza a operar a partir del
axioma de la gramática y procura desarrollar por izquierda el árbol de derivación sintáctica a medida que la
sentencia es leída. Si este proceso puede ser continuado hasta completarse la lectura de la cadena significa
que la misma responde a las producciones de la gramática y, por lo tanto, es aceptada.
Dada una gramática GIC G = (ΣT , ΣN , S, P) se debe construir un autómata con pila AP = (ΣT , ΣT∪ΣN∪{#},
{p, q, r}, p, #, {r}, f) de la siguiente forma:

El símbolo en la cima de pila es el que conduce el proceso de validación. C

- Cada vez que ese símbolo es un no terminal A, se reemplaza en la pila por la cadena α
- Cada vez que en el tope de pila hay un terminal se espera encontrar el mismo símbolo en la cadena
de entrada, y es cancelado.
Se prosigue así hasta que la sentencia de entrada es completamente leída y en esa condición la pila debería
estar vacía. Aquí debe observarse que pueden haber múltiples reglas de reescritura con el mismo símbolo
no terminal en el primer miembro, y esto hace que se trate nuevamente de un APND.
Se los suele llamar LL básicos, por Left-Left, ya que la cadena es leída de izquierda a derecha y el proceso
que desarrolla corresponde al de una derivación por izquierda.
Analizadores Sintácticos Ascendentes
Los Analizadores Sintácticos Ascendentes (ASA) son denominados Bottom-Up Parsers y comprueban
la validez de la sentencia operando de abajo hacia arriba. Es decir, recorren el árbol de derivación sintáctica
desde las hojas hacia su raíz, que es el axioma de la gramática y, en general disponen de mayor poder de
reconocimiento que los analizadores descendentes.
Dada una gramática GIC G = (ΣT , ΣN , S, P) se debe construir un autómata con pila AP = (ΣT , ΣT∪ΣN∪{#},
{p, q, r}, p, #, {r}, f) de la siguiente forma:

Se los suele llamar LR básicos, porque las cadenas son leídas de izquierda a derecha (Left) y se sigue un
proceso de reducción por izquierda. Puede comprobarse que a una reducción por izquierda le corresponde
una derivación por derecha (Right) y de allí el segundo carácter de la denominación LR.
• En cada intervalo de tiempo, se presenta la opción de desplazar un nuevo símbolo a de la entrada a la
pila, o reducir una cadena α ya almacenada en la pila; por ello se llama a estos analizadores por
reducción y desplazamiento.
• Para poder hacer la reducción se debe reconocer la cadena α en la pila, lo que implica identificar
anticipadamente varios símbolos en la pila; esto plantea una contradicción con la concepción de la
memoria tipo lifo en la que solo se hace visible el símbolo que se encuentra en su tope. El problema se
resuelve apelando al no determinismo del ap, con lo cual se puede asumir en la práctica a la pila como
una estructura híbrida que opera como tal, pero admite la observación de todo su contenido.
• En la reducción de la cadena α, seguramente se presentarán diferentes opciones ya que es probable
que numerosas producciones tengan a α en su segundo miembro. Por su lado, en el desplazamiento
desde la entrada hacia la pila, también se presenta siempre la opción de seguir apilando símbolos de
entrada o efectuar una reducción.
• La cadena será aceptada si a través de su completa lectura pudo conducirse la reducción hasta dejar en
la pila solo el axioma de la gramática.
Analizadores Sintácticos con Preanálisis
Preanálisis: Técnica de programación para hacer que el APND funcione en forma determinista. Implica
conocer anticipadamente los próximos k símbolos a ser leídos por el autómata, pudiendo predecir cuál
de todas las posibles producciones aplicables es la conducirá a la aceptación.
En otras palabras, consiste en “espiar uno o más símbolos de la entrada” sin leerlos (preanalizar), para
decidir cuál de las producciones conviene utilizar frente a alternativas no deterministas que se presente.
Con esta técnica pueden desarrollarse algoritmos de análisis sintáctico que pueden programarse en forma
eficiente los llamados analizadores sintácticos predictivos:
• LL(k): Left to right read and leftmost derivation ASD
• LR(k): Left to right read and rightmost derivation ASA
Donde k es la cantidad de símbolos de entrada a preanalizar.
En el caso de los analizadores LR(k), se mencionan, a continuación, algunos de los más importantes:
• LR(0): No utiliza preanálisis, por lo que es apropiado cuando las producciones de las gramáticas no
generan transiciones alternativas. Es el más fácil de implementar y, a la vez, el que dispone de menor poder
de reconocimiento.
• SLR(1): Utiliza un solo símbolo de preanálisis y su nombre (del inglés) significa Simple LR.
• LR(1): Es un analizador ascendente LR clásico que utiliza un símbolo de preanálisis. La implementación
de su AP conduce a estructuras de datos muy grandes y ha justificado el desarrollo de generadores
automáticos.
• LALR(1): Su nombre proviene del inglés Look-Ahead LR, en el que se combina la potencia del LR(1) con
la simplicidad y eficiencia del SLR (1). Éste es el método que utiliza YACC para la generación de
analizadores sintácticos en C.
UNIDAD N°6 – AUTÓMATA LINEALMENTE ACOTADO Y MÁQUINA DE TURING
Autómata Linealmente Acotado
Al agregarle al AFDB la posibilidad de grabar en su cinta, adquiere una memoria lineal finita de acceso
aleatorio, ya que moviendo su cabezal a derecha y a izquierda puede acceder a cualquier celda de la cinta.
Se obtiene una nueva máquina abstracta llamada Autómata Linealmente Acotado (ALA). La capacidad
de grabar implica la ampliación del alfabeto de cinta Γ con la incorporación de símbolos auxiliares reunidos
en un nuevo alfabeto Ω. Queda definido como:
ALA = ( Σ, Γ, Q, q0 , A, f )
cuyos componentes son:
- Σ = alfabeto de símbolos de entrada
- Γ = Σ ∪ {├, ┤} ∪ Ω = alfabeto de símbolos de cinta
- Q = conjunto finito y no vacío de estados posibles
- q0∈Q = estado inicial de funcionamiento
- A⊆Q = conjunto de estados de aceptación
- f : Q x Γ → Q x Γ x {I, D, N, P} = función de transición
Funcionamiento
Siempre iniciando su operación desde el estado inicial q0 con su cabezal sobre el símbolo de inicio de cinta
(el símbolo de más a la izquierda), el autómata:
1. Lee un símbolo de entrada e.
2. Graba un símbolo de salida s.
3. Transita a un estado q.
4. Mueve el cabezal a Izquierda, Derecha, No lo mueve o Para.
5. Repite 1, 2, 3 y 4 hasta ejecutar una instrucción de Parada.
6. Al detenerse, decide si acepta o no la cadena de entrada.
Durante su funcionamiento, el ALA:
• No puede mover su cabezal a la izquierda si está leyendo BOT, y no puede mover su cabezal a la
derecha, si está leyendo EOT.
• Podría quedar atrapado en un ciclo infinito y no terminar.
• Siempre para aceptar la cadena de entrada, se pedirá que al menos la haya leído una vez. Para eso
pediremos que se detenga en un estado de aceptación con su cabezal en EOT.
Aceptación o Reconocimiento de Cadenas y Lenguajes
Aceptación o reconocimiento de cadenas (1): un ALA acepta o reconoce una cadena de símbolos de
entrada α∈Σ*, si puede detenerse (Parar) en un estado de aceptación qf∈A con su cabezal de lecto-escritura
ubicado sobre el símbolo de fin de cadena EOT ( ┤).
Lenguaje reconocido L(ALA) (1): conjunto de cadenas de símbolos de entrada que son reconocidas por
el ALA.
Si se tiene en cuenta la cadena que quedó en la cinta luego del procesamiento del ALA, puede verse a esta
máquina como Ejecutora de Procedimientos: ALA: Σ* → Γ*
Configuración o Descripción Instantánea
Kt = (qt,├ αt┤, n)
qt ∈ Q → estado actual en el instante t
αt ∈ Γ ∗ → contenido de la cinta en el instante t
n ∈ N → posición del cabezal sobre la cinta, 0 ≤ n ≤ |αt |+1
Configuración Inicial:
K0 = (q0, ├ α0┤, 0)
Configuración Final:
Kn = (qn, ├ αn┤, m) con ALA detenido
Si qn∈A y m=|αn |+1, ésta ES una configuración de aceptación. Como siempre, la configuración es una
foto en t del proceso sobre α.
Movimiento: cambio de una configuración a otra: (qt ,├ αt┤, nt ) Ͱ (qt +1 ,├ αt +1 ┤, nt+1)
Si es posible pasar de una a otra en una transición de f.
Movimiento generalizado entre configuraciones: (qt ,├ αt┤, nt ) Ͱ* (qt +k ,├ αt +k ┤, nt+k) Si es posible
pasar de una a otra en k transiciones de f.

Aceptación o reconocimiento de cadenas (2): un ALA acepta o reconoce una cadena de símbolos de
entrada α∈Σ*, si puede moverse desde una configuración inicial a una configuración final de aceptación y
detenerse (Parar).
(q0 ,├ α ┤, 0) Ͱ* (qf ,├ β ┤, |β|+1) con qf∈A
Si se tiene en cuenta la cadena que quedó en la cinta luego del procesamiento del ALA, puede verse a esta
máquina como Ejecutora de Procedimientos: ALA: Σ* → Γ*

Máquina de Turing
Definición: Una Máquina de Turing, es un modelo matemático (máquina abstracta) denotado por:
MT = ( Σ, Γ, Q, q0 , A, f , ƀ )
cuyos componentes son:
- Σ = alfabeto de símbolos de entrada
- Γ = Σ ∪ {ƀ} ∪ Ω = alfabeto de símbolos de cinta – ƀ=blanco
- Q = conjunto finito y no vacío de estados posibles
- q0∈Q = estado inicial de funcionamiento
- A⊆Q = conjunto de estados de aceptación
- f : Q x Γ → Q x Γ x {I, D, N, P} = función de transición

En otras palabras, se trata de un ALA a cuya cinta se le permite extenderse más allá de la cadena a ser
procesada; por ello, se debe definir un símbolo que, por defecto, ocupará el resto del medio de
entrada/salida y usualmente se utiliza para este fin el b (blanco). La ausencia de límites implica que este
medio se extiende ahora hasta el infinito, conformando una enorme área de trabajo o memoria auxiliar.
Funcionamiento
Siempre iniciando su operación desde el estado inicial q0 con su cabezal sobre el primer símbolo de la
cadena de entrada, la máquina:
1. Lee un símbolo de entrada e.
2. Graba un símbolo de salida s.
3. Transita a un estado q.
4. Mueve el cabezal a Izquierda, Derecha, No lo mueve o Para.
5. Repite 1, 2, 3 y 4 hasta ejecutar una instrucción de Parada.
6. Al detenerse, decide si acepta o no la cadena de entrada.
Durante su funcionamiento, la MT puede
• Modificar nuevas celdas de la cinta infinita llena con espacios en blanco si le es necesario para su tarea
⇒ memoria lineal infinita.
• Quedar atrapada en un ciclo infinito y no terminar
• Aceptar una cadena sin tener que leerla completamente con sólo detenerse en un estado de aceptación.
Aceptación o Reconocimiento de Cadenas y Lenguajes
Aceptación o reconocimiento de cadenas (1): una MT acepta o reconoce una cadena de símbolos de
entrada α∈Σ*, si puede detenerse (Parar) en un estado de aceptación qf∈A.
Lenguaje reconocido L(MT) (1): conjunto de cadenas de símbolos de entrada que son reconocidas por la
MT.
Si se tiene en cuenta la cadena que quedó en la cinta luego del procesamiento de la MT, puede verse a esta
máquina como Ejecutora de Procedimientos: MT: Σ* → Γ*
Configuración o Descripción Instantánea
Configuración o Descripción Instantánea
Kt = (qt, ƀαt ƀ, n)
qt ∈ Q → estado actual en el instante t
αt ∈ Γ ∗ → contenido de la cinta en el instante t
n ∈ N →: posición del cabezal sobre la cinta, -∞ < n < -∞
Configuración Inicial:
K0 = (q0 , ƀα0 ƀ, 1)
Configuración Final:
Kn = (qn , ƀαn ƀ, m) con MT detenida.
Si qn∈A, ésta ES una configuración de aceptación. Como siempre, la configuración es una foto en t del
proceso sobre α.
Movimiento cambio de una configuración a otra: (qt , ƀαt ƀ, nt ) Ͱ (qt +1 , ƀαt +1 ƀ, nt+1)
Si es posible pasar de una a otra en una transición de f.
Movimiento generalizado entre configuraciones: (qt , ƀαt ƀ, nt ) Ͱ* (qt +k , ƀαt +k ƀ, nt+k)
Si es posible pasar de una a otra en k transiciones de f.
Otra forma de mostrar una configuración de un MT es:
Aceptación o reconocimiento de cadenas (2): una MT acepta o reconoce una cadena de símbolos de
entrada α∈Σ*, si puede moverse desde una configuración inicial a una configuración final de aceptación y
detenerse (Parar).
(q0 , ƀ α ƀ, 0) Ͱ* (qf , ƀ β ƀ, m) con qf∈A
Si se tiene en cuenta la cadena que quedó en la cinta luego del procesamiento de la MT, puede verse a esta
máquina como Ejecutora de Procedimientos: MT: Σ* → Γ*

Interpretaciones de ALA y MT
Tanto el ALA como la MT, pueden interpretarse de dos formas:
1. Reconocedora de Lenguajes
ALA → reconoce lenguajes TIPO 1 (LDC)
MT → reconoce lenguaje TIPO 0 (LEF)
Un lenguaje L definido sobre el alfabeto ΣE, es reconocido por un ALA o por una máquina de Turing M si:

Aquí debe tenerse en cuenta que ├─* denota una cantidad finita de movimientos y, por consiguiente, de
intervalos de tiempo, lo que implica que ante cualquiera de las cadenas α∈ L la máquina se detiene en un
estado de aceptación qA∈A. En este caso, se dice que L = L(M), es decir que el lenguaje definido sobre el
alfabeto ΣE es reconocido por la máquina M (en el caso del ALA, k debe indicar el fin de cinta ┤). Por el
contrario, si el estado final alcanzado al detenerse no es de aceptación, es decir que qA ∉ A, significa que
la máquina M ha rechazado la cadena α. Puede también darse el caso que la máquina no se detenga con
α, entonces se dirá que M es indiferente a α ya que ni la acepta ni la rechaza. En esta última condición, la
acción de M no determina un algoritmo.
2. Ejecutora de Procedimientos

Se trata de procedimientos efectivos que, a partir de una cantidad finita de movimientos, convertirán la
cadena inicial α en otra cadena final β que cumplirá ciertas condiciones. Se trata de máquinas que pueden
caracterizarse como traductoras, por establecer una relación entre entrada y salida. Para una MT:
(q0, α, 1) ├─* (qf, β, k), donde q0,qf ∈ Q, α∈ΣE * , β∈Γ
hay situaciones en las que el objetivo es el propio proceso y no una cierta cadena final β, tratándose muchas
veces de casos en que la máquina cumple infinitas veces un mismo ciclo. En estos casos, interesa la
sucesión de estados que recorre reiteradamente el autómata, ya que los mismos suelen estar asociados a
condiciones de control; la salida del autómata no está representada por la cadena final β sino por la sucesión
de los estados alcanzados en un cierto orden. Por ejemplo:
(p, α, 1) ├─∞ … [p, q, r, s, t ], p, q, r, s, t ∈ Q, α ∈ ΣE *
Halting Problem o Problema de la Parada
Tanto el ALA como la MT, pueden no detenerse:
Autómata Linealmente Acotado Si bien al ALA puede no detenerse, al ser su cinta y alfabetos finitos, en
algún momento repetirá una configuración, por lo que se podría detectar que ha entrado en un bucle.
Máquina de Turing La MT también puede no detenerse, pero al ser su cinta infinita, no puede siempre
saberse si entró en un bucle. Se dice que el problema de la detención de la MT es indecidible (en el sentido
de Gödel). Esto es, no existe un algoritmo (o una MT) que decida si otra MT se detiene.
Tesis de Turing-Church. Church había definido qué es una función computable y demostrado que existen
funciones no calculables. Turing conjeturó que su máquina es capaz de computar cualquier función
calculable y logró demostrar que la MT podía calcular cualquiera de las funciones computables de Church.
Hoy se considera que la MT es el modelo formal más general de computación (en cuanto a su poder de
cálculo), por lo que se dice que un problema es computable si y sólo si, puede ser resuelto por una
Máquina de Turing.
Variantes de la Máquina de Turing
Máquina de Turing Modular
Se refiere a la construcción de autómatas mayores a partir de aislar y asignar sus funciones principales a
máquinas individuales específicas, que luego son incorporadas a la principal.
La idea es crear pequeñas máquinas de Turing que realicen funciones sencillas, para luego combinarlas
unas con otras, para “programar” problemas más complejos, de manera más sencilla.
Máquina de Turing Universal
MT que recibe en su cinta una descripción codificada de otra máquina de Turing y produce como resultado
de su ejecución el mismo resultado que produciría la MT descripta en la cinta. Esta máquina recibe el nombre
de universal por ser capaz de simular el comportamiento de cualquier otra máquina de Turing; es decir,
puede leer otra MT convenientemente codificada en su cinta y la entrada de ésta, para emular su
funcionamiento.
Máquina de Turing Generalizada
Se incorpora más “hardware” a su versión original. En particular, se diseña esta nueva máquina con un
número arbitrario (pero finito) de cintas de entrada/salida que, a su vez, pueden tener múltiples cabezales
de lectura/escritura.
Máquina de Turing No Determinista
MT con función f : Q x Γ → P (Q x Γ x {I, D, N, P})
Con esta función podría en cada paso hacer varias cosas distintas en forma simultánea. En todos los casos
siempre se ha encontrado una MT determinista tradicional de una sola cinta, EQUIVALENTE.
COMPLEJIDAD DE LA MÁQUINA DE TURING
La Ciencia de la Computación considera que un problema es computable si y sólo sí puede construirse una
MT que lo resuelva: una solución. Ahora, una vez establecida la computabilidad de un problema, queda
como una cuestión importante: ¿es la mejor solución?

Si bien deseamos estudiar la complejidad de

los problemas, en realidad lo que se aborda
es el estudio de la complejidad de las
soluciones que hemos podido construir para
esos problemas, en el convencimiento de que
problemas complejos requieren soluciones
complejas (Análisis de Algoritmos).
En Informática podemos hablar en principio de dos tipos de complejidad de las soluciones, cuyo estudio
e importancia obedecerán a los distintos objetivos que se persigan:
-Complejidad Lógica: Mide la sencillez de la solución que hemos podido construir para el problema; qué
tan fácil resulta de entender y, consecuentemente, de modificar. Importante en una empresa de Sistemas.
-Complejidad de Recursos: Mide cuántos recursos insume la ejecución de la solución que hemos
construido; los recursos críticos suelen ser el tiempo que demora la solución en dar el resultado y el
espacio de memoria necesario para alojarla. Importante en Computación y en Sistemas.

Para lograr precisión, objetividad y reproducibilidad se recomienda:

• Utilizar un modelo de computación uniforme y bien conocido para expresar la solución: Máquina de Turing
determinista de una cinta.
• Un problema puede tener más de una Máquina de Turing que lo resuelva. Se considerará que la
complejidad del problema está dada por la complejidad de la mejor MT solución construida.
• En el caso de la complejidad computacional, medida por los recursos que insume la solución, claramente
estos recursos (tiempo y espacio) dependen de los datos de entrada en cada corrida. Por ello:
• Del mejor, peor y caso promedio, se tomará el peor caso.
• Se establecerá cómo cambian los recursos insumidos en función del largo los datos de entrada
como una medida de la complejidad, esto es, se busca una función f(n).
Complejidad Lógica
Complejidad Estructural de Shannon
Es un método para establecer una complejidad lógica: la complicación intrínseca de la solución.
Shannon propuso una medida de complejidad para la máquina de Turing, que mide la cantidad de
conexiones en su grafo (≅ número de flechas):
Complejidad = |Q| × |Γ|
También demostró equivalencias interesantes sobre las máquinas de Turing:
Teorema 1: Cualquier MT con |Γ|=m y |Q|=n puede ser simulada por una MT’ con sólo dos estados y
4.m.n+m símbolos. Toda máquina universal de Turing requiere al menos dos estados.
Teorema 2: Cualquier MT con |Γ|=m y |Q|=n puede ser simulada por una MT’ con sólo dos símbolos y
menos de 8.m.n estados.
Complejidad Ciclomática
En la década de 1970 se desarrolló la programación estructurada y se especificó como una posible medida
de la complejidad de los algoritmos, el número de regiones cerradas en un diagrama de flujo estructurado,
esto es, en el mapa de su grafo plano. Sabemos por Eüler que si G = (N, S) es un multigrafo plano, su mapa
tendrá:
Regiones Cerradas = |S| - |N| + 1
En Ingeniería de Software, esta medida de complejidad se denomina hoy complejidad ciclomática.
Complejidad Algorítmica
Otra propuesta para medir la complejidad de un problema, es la de Gregory Chaitin que la propone como
“el largo del programa más corto escrito para resolver el problema”. Esta medida tiene no pocos
inconvenientes, ya que el largo del programa varía según el lenguaje y el compilador utilizado para
construirlo.
Siguiendo las ideas del matemático ruso Kolmogorov, aunque Gregory lo negaría, esta visión también tiene
mucho que ver con el concepto de aleatoriedad y genera aún controversias (ver el número Ω de Chaitin).
Complejidad Computacional
En las Ciencias de la Computación, el enfoque dado a la complejidad es la Teoría de la Complejidad
Computacional, que identifica a la complejidad con los recursos (tiempo y espacio) requeridos por la
solución (operativa).
Ya se indicó el uso de la Máquina de Turing como un modelo formal y conocido de computación en el cual
desarrollar las soluciones a los problemas. También se señaló que lo que se busca es cómo cambian los
recursos utilizados para la ejecución de la MT según el largo de los datos de entrada: una función. Por
ejemplo, un algoritmo para “ordenar un arreglo de diez números de menor a mayor”, tardará más tiempo y
ocupará más espacio al querer operar con un arreglo de cien mil números. Pero el algoritmo es el mismo,
por lo cual su complejidad no debería cambiar.
Complejidad Temporal
Es una función T(n) que determina la cantidad de movimientos (o unidades elementales de tiempo) que
utiliza en resolver un problema con datos de entrada α de largo |α|=n.
Complejidad Espacial
Es la función E(n) que determina la cantidad de celdas de cinta (su memoria) utilizadas para resolver un
problema con datos de entrada α de largo |α|=n.
Si bien estas dos medidas son independientes, como el cabezal de una MT siempre se mueve de a una
celda, en general:
E(n) ≤ T(n) + 1
Órdenes de Complejidad
Dado un problema computable, se pueden construir varias MT distintas que lo resuelvan; para ellas, habrá
distintas complejidades T(n) y E(n), pero salvo errores, en general serán todas ellas de similar orden. El
orden de una función f, se denota con la notación O grande o Big O:
f(n)∈O(g(n)) ↔ ∃n0∈N, k∈R / ∀n≥n0 : f(n) ≤ k . g(n)
 esto es, la función f es de orden g si está acotada superiormente por k.g (k constante) a partir de un
valor n0 en adelante.
𝒇𝒇(𝒏𝒏)
De la definición resulta ≤ 𝒌𝒌, lo que dice que ambas funciones crecen con la misma tasa o velocidad,
𝒈𝒈(𝒏𝒏)

desde algún n0.

Podemos ganar aún más en objetividad. Si bien un problema puede tener varias MT que lo resuelvan con
sus T(n) y E(n), al tener ellas similar orden, podremos hablar del orden de la complejidad de la solución:

Clases de Problemas
Clase P: problemas que pueden resolverse con una máquina de Turing Determinista en tiempo polinómico
o menor.
Clase NP: problemas que pueden resolverse con una máquina de Turing NO Determinista en tiempo
polinómico o menor.
Clase NP-Completos: subproblemas de la clase NP a los que cualquier otro problema de NP puede
reducirse (conversión) en tiempo polinómico.
Como la MTD es un caso particular de la MTND, es claro que P ⊆ NP. Por definición, también NP-completos
⊆ NP. El primer problema NP-completo, formulado por Cook, es el de satisfactibilidad lógica: SAT
Uno de los problemas más importantes, aún no resuelto, de las matemáticas y la computación es el
determinar si también NP ⊆ P, o sea : ¿ P = NP ?
Esto está en investigación actualmente y se han definido muchas otras clases de complejidad.
Medición de la complejidad
Una vez definidos los indicadores de complejidad, estos deben ser evaluados para cada caso particular.
1. Los indicadores de complejidad temporal y espacial, pueden obtenerse a través de un proceso inductivo
que se apoya en un estudio detallado del algoritmo utilizado, permitiendo definir expresiones generales que
serán válidas para cualquier tamaño del problema estudiado
2. El algoritmo es lo suficientemente enmarañado como para que no sea fácil o posible obtener las
expresiones de complejidad a través de su análisis. En estos casos, se hacen evaluaciones de los
indicadores de complejidad resultantes para ciertas dimensiones del problema, se proponen grados para el
polinomio que representa su complejidad y se calculan algebraicamente los coeficientes del polinomio.
3. Los indicadores de complejidad no dependen únicamente de la dimensión del problema sino también de
la forma en la que se presentan los datos. Se suelen utilizar dos valores de complejidad: a) el que
corresponde a la condición extrema que demanda el máximo esfuerzo y representa una cota superior a la
complejidad del problema y b) el de la condición de trabajo más probable (una situación media).
Las expresiones de complejidad buscadas tienen las finalidades de permitir: i) conocer los órdenes de las
complejidades de los problemas, ii) cuantificar esas complejidades para ciertas dimensiones específicas y
poder hacer previsiones referidas a los recursos necesarios para resolverlos y iii) comparar entre sí
diferentes problemas o distintas formas de abordar un mismo problema.
 UNIDAD N°8 – INTRODUCCIÓN A LA SEMÁNTICA DE LOS LENGUAJES
En el estudio de los lenguajes se distinguen la gramática y la semántica. La gramática se ocupa del análisis
de las estructuras de las frases, y dentro de la gramática, la morfología analiza las formas que toman las
palabras, la sintaxis se ocupa de cómo combinar las palabras para formar frases correctas y la fonética trata
al lenguaje hablado. Por su parte, la semántica se ocupa del estudio del significado que es atribuible a
expresiones sintácticamente bien formadas.
En base a lo anterior, se entiende por semántica de un lenguaje, al conjunto de reglas que especifican
el significado de toda sentencia sintácticamente correcta, escrita en el mismo.
Enfoques de la Especificación Semántica de los Lenguajes

Especificación Semántica Formal: definir el significado de las sentencias de un programa y de los

programas completos mediante una formulación al estilo matemático. entendemos por significado de un
programa a su comportamiento al ejecutarlo.
se deberá lograr explicar cuál es el resultado obtenido al ejecutar el programa construido (qué hace, cómo
lo hace o cuáles serán sus propiedades cuando se lo ejecuta), utilizando símbolos y procedimientos al estilo
matemático: signos bien definidos, funciones, conjuntos, procedimientos, deducciones, modelos
matemáticos como máquinas abstractas, etcétera.
Se necesita especificación formal, entre otras cosas para:
a) Diseño de nuevos lenguajes de programación, registrando decisiones sobre construcciones
particulares y facilitando la identificación de errores u omisiones.
b) Necesidad de estandarización de los lenguajes mediante la publicación de su semántica de un modo
universalmente reconocible.
c) Diseño e implementación de los procesadores de los nuevos lenguajes (compiladores o intérpretes) y
de los generadores de compiladores.
d) Necesidad de identificar posibles ambigüedades en las implementaciones de procesadores de
lenguajes de programación o en sus documentos descriptivos.
e) Comprensión de los lenguajes por parte de los programadores.
f) Verificación de propiedades de programas a través de pruebas de corrección (verificación) o de la
información relacionada con su ejecución.
Se distingue verificación (corrección del programa construido) de validación (adecuación de la especificación
al problema). Por su lado, la verificación puede ser estática (búsqueda de errores del programa mirando su
código fuente) o dinámica (búsqueda de errores ejecutando el programa).
Metalenguajes
Semántica Operacional (Modelos)
Se trata del enfoque semántico más antiguo, más utilizado por ser intuitivo, fácilmente aplicable y por
describir al comportamiento observable. Describe cómo interpretar un programa a través de una
secuencia de pasos de cálculos u operaciones.
Esto puede hacerse asociando código de máquina a cada regla sintáctica. Su descripción es muy cercana
a su implementación.
Se utilizó por primera vez en la definición de Algol 68 y posteriormente para construir prototipos de
procesadores de lenguajes, como en el caso de la descripción del lenguaje PL/1 (1969).
Semántica Denotacional (Modelos)
Entiende que el significado de un programa puede describirse en términos de aplicación de entidades
matemáticas (funciones) a sus argumentos (denotación). La idea es describir el significado de una
sentencia por una función, que actuando sobre algún conjunto (con elementos como variables, memoria,
tipos, etc.) produzca como salida el resultado que debería dar la sentencia (el qué).
A través del uso de conjuntos y funciones, se representan la mayoría de los conceptos, tales como memoria,
variables, tipos, y otros para alcanzar un elevado nivel de abstracción.
Se hace más hincapié en el resultado de la ejecución que en la forma que esta es llevada a cabo.
Se empleo para especificar la semántica de programas como ADA y pascal.
Semántica Axiomática (Propiedades)
Se pretende describir el lenguaje de programación como un Sistema Axiomático (términos primitivos,
axiomas, definiciones) que permita obtener el resultado de la ejecución del programa como una
deducción desde los datos de entrada (un teorema).
Esta más orientado a la demostración de propiedades de un programa, no a algún método de
implementación.
Semántica Algebraica (Propiedades)
El lenguaje de programación se presenta como una estructura algebraica (elementos, conjuntos y
funciones), orientada a definir los tipos y estructuras de datos como conjuntos de valores, y las
operaciones que son posibles entre ellos. Es equivalente al enfoque axiomático pero basado en álgebra;
se acerca al enfoque Denotacional, ya que intenta describir el significado de las sentencias como el resultado
de aplicar esas operaciones a las estructuras de datos.
Demostración de propiedades, no induce a implementación
Semántica de Acciones (Propiedades)
La definición de la semántica del lenguaje está basada en un conjunto de acciones, que son las
operaciones habitualmente previstas en los lenguajes de programación. Con este fin, se definen
primitivas para la asignación y declaración de variables y la combinación de instrucciones mediante
control de flujo secuencial, condicional e iterativo donde se establecen las propiedades que su aplicación
verifica sobre las variables.
Se acerca al enfoque operacional.
Cercano a la implementación, induce a implementación
Gramáticas con Atributos
Las gramáticas atribuidas son la forma habitual de especificar la semántica de los lenguajes de programación
comerciales.
Agrega a la GIC del lenguaje un conjunto de propiedades de los símbolos gramaticales (los atributos de
esos símbolos de ΣT∪ΣN), reglas para determinar los valores de esas propiedades y restricciones que se
imponen a las propiedades y a su cálculo.
Este enfoque permite hacer buena parte del análisis semántico guiado por la sintaxis que está definida en
la gramática formal del lenguaje.
Definición: Dada una GIC = (ΣT , Σ N , S, P) llamaremos atributo a una propiedad asignable a los
símbolos gramaticales de la gramática (Σ =ΣT∪Σ N) que tendrá un nombre y un valor de un conjunto de
posibles valores bien definido.
Notación: si a∈Σ y XYZ es un atributo de a, se denotará a.XYZ.
Ejemplos: Supongamos que un identificador ID es un símbolo gramatical y que puede tener como atributos
un nombre, una dirección de memoria, un valor contenido en ella y un tipo de dato que puede contener;
entonces los podríamos denotar ID.nombre, ID.dirección, ID.valor, ID.tipo
Una gramática con atributos es una tupla:
GA = (ΣT , Σ N , S, P, A, R, C)
donde:
- (ΣT , Σ N , S, P) es una gramática independiente del contexto.
- A : conjunto de atributos asociados a los símbolos gramaticales de Σ =ΣT∪Σ N .
- R : conjunto de acciones o reglas semánticas asociadas a las producciones de P.
- C : conjunto de condiciones asociadas a las producciones de P y que deben cumplir los atributos de
A para su cálculo.
Funcionamiento
El análisis sintáctico de una cadena α∈Σ𝐓𝐓∗ de símbolos terminales, determina si pertenece al lenguaje L
generado por la gramática (si está bien escrita según la reglas del lenguaje). Para hacer esto, construye una
derivación o un árbol de análisis sintáctico de α; cada vez que una producción de P es aplicada, se ejecutarán
las reglas semánticas en R para determinar el valor de los atributos de A involucrados, y se verificará la
satisfacción de las condiciones indicadas en C para ellos.
Clasificación de Atributos
Los atributos representan propiedades de los símbolos terminales y no terminales de una gramática y su
naturaleza varia según la información que contiene y la fase de procesamiento en la que se encuentren.
Según el momento en el cual se determinan sus valores:
- Atributo estático: en tiempo de compilación.
- Atributo dinámico: en tiempo de ejecución.
Según la forma de calcular el valor con el árbol de derivación:
-Atributo sintetizado: utilizando el valor de los atributos de los nodos hijos a los del no terminal en un nodo
– AS(Σ):ASA
- Atributos heredados: utilizando el valor de los atributos del nodo padre y de los hermanos (aquellos a la
izquierda en la producción al nodo en cuestión) – AH(Σ): ASD