Teoría de AutómatasLa computación, muy avanzada hoy en día, sienta sus bases sobre una sólida plataforma desarrollada con mucho esfuerzo e investigación, un área importante es el trabajo con los lenguajes de programación, cuyas raíces están en la teoría de autómatas y lenguajes formales. Esta asignatura forma parte del área fundamental de la carrera de Ingeniería en Informática correspondiente al sexto semestre. Esta asignatura tiene su importancia en que señala los aspectos básicos de los lenguajes computacionales, así como nos muestra de manera general el trabajo interno de los sistemas de computación en lo referente al tratamiento de cadenas y lenguajes, los contenido que se cubren son principalmente los autómatas finitos, autómatas de pila, lenguajes independientes de contexto, maquinas de turing como reconocedores de lenguajes. Sea bienvenido al presente curso y no dude en contactar a su profesor en caso de necesitar resolver cualquier inquietud. Saludos y éxitos!!!

Tabla de contenidos 1 Objetivo General 2 Objetivos Especificos

3 Bibliografia

4 Desarrollo del Aprendiza

o 4.1 Capitulo 1: Automatas Finitos

4.1.1 Datos Generales

4.1.2 DESARROLLO

4.1.3 Construcción de autómatas

4.1.4 Transformación de un AFN en un AFD.

o 4.2 Capitulo 2 Expresiones y Lenguajes Regulares

4.2.1 Datos Generales

4.2.2 Conversión de una expresión regular en autómata finito

4.2.3 Algoritmo de transformación de una expresión regular en un AFN

o 4.3 Capitulo 3 Analisis Lexico

4.3.1 Datos Generales

o 4.4 Capitulo 4 Automatas a Pila

4.4.1 Datos Generales

o 4.5 Capitulo 5 Lenguajes Independientes de Contexto

4.5.1 Datos Generales

o 4.6 Capitulo 6 Maquinas de Turing

4.6.1 Datos Generales

4.6.2 Construcción de máquinas de turing

Objetivo GeneralDar al estudiante una visión global del trabajo de los autómatas y su aplicación en los lenguajes de programación.

Objetivos Especificos Conocer como funcionan los lenguajes. Especificar lenguajes regulares y autómatas finitos para reconocimiento.

Escribir programas de reconocimiento léxico.

Especificar lenguajes independientes de contexto y autómatas de pila para reconocimiento.

Construir máquinas de turíng para reconocer lenguajes.

Escribir gramáticas de contexto libre.

Escribir programas de análisis sintáctico

BibliografiaTexto Base

Hopcroft, J., et All, Introducción a la Teoría de Autómatas, Lenguajes y Computación, Segunda Edición, Adison Wesley, Madrid, 2002

Este libro tiene un espectro amplio en cuanto a que cubre desde los detalles hasta aspectos avanzados de cada tema, está expresado en términos sencillos y solo en casos necesarios recurre a expresar con formalismos los diferentes aspectos que trata.

Texto Complementario

Kelley, D. Teoria de Autómatas y Lenguajes Formales, Prentice Hall, Madrid 1995Escogido por los temas que cubre y principalmente por la amplia gama de ejercicios que resuelve y plantea, ofrece un capitulo especial (el número cero) dedicado a aquellos que tienen problemas con las matemáticas necesarias para abordar la materia. Su metodología la basa en definiciones cortas, ejercicios resueltos con explicaciones detalladas y muchos ejercicios planteados.

Construcción de autómatas

Diseñar un AFD que acepte identificadores que inicien siempre con un guión bajo y luego puedan contener letras o dígitos.

Inicialmente debemos asociar la condición inicial al estado inicial, esto significa que desde el primer estado al segundo estado únicamente puede existir una transición que etiquetada con guión bajo

Una vez en el estado dos, se puede avanzar hacia el estado tres con una transición etiquetada con letra (L) o con digito (D).

Ahora es necesario que la cadena pueda tener mas letras o más dígitos, esto se puede conseguir haciendo que desde el estado 3 salga una arista etiquetada con letra (L) hacia otro estado (que puede ser el mismo estado 3). Lo mismo hay que hacer para reconocer más dígitos.

Desarrollemos ahora otro autómata que reconozca cadenas de letras (sobre el alfabeto {a,b}) en las que nunca puedan ir dos a’s seguidas

La condición inicial no esta asociada al estado inicial, el autómata puede empezar con una letra a o con una letra b

Ahora puede tener otra letra b con la que regresa al estado 1. Note que siempre termina en el estado 2.

Es posible construir autómatas que tengan transiciones vacías, es decir que sus aristas no tienen como etiqueta símbolos del alfabeto del autómata, en su lugar tienen vacío (ε), generalmente las transiciones vacías se utilizan para unir autómatas, como en el caso de la figura 2.19 de la página 81 del texto base.

Transformación de un AFN en un AFD.

El procedimiento consiste en agrupar los conjuntos de estados que tengan entradas y salidas (aristas) comunes, para ello se crea una tabla de transiciones (representación del AFD), esta matriz (llamada Matriz_de_D) tiene como índices el conjunto de estados (con aristas comunes) y los elementos del alfabeto.

Son necesarias tres operaciones cuyos resultados se requieren al aplicar el algoritmo de transformación:

Cerradura-ε de s.- Equivale al conjunto de estados del AFN que se pueden alcanzar des-de s sin consumir símbolos de la entrada (o lo que es lo mismo con transiciones-e). Esta operación devuelve un conjunto de elementos (estados).

Cerradura-e de T.- Sea T un conjunto de estados, esta operación equivale al conjunto de estados del AFN que se pueden alcanzar desde cada s en T sin consumir símbolos de la entrada (o lo que es lo mismo con transiciones-e). Esta operación devuelve un conjunto de elementos (estados).

Mueve (T, a).- Equivale al conjunto de estados que se pueden alcanzar con un símbolo a (arista etiquetada con a ) desde algún estado s de T. Esta operación devuelve un conjunto de elementos (estados).

En caso de tener problemas, recuerde que s es un estado; T es un conjunto de estados en donde cada uno en su momento se representa por s; a es un símbolo que etiqueta una arista que va desde un estado a otro.

Por conveniencia se denominan el AFN como N y el AFD como D.

Algoritmo 1. Inicio 2. A = Cerradura-ε de s0 /* Cerradura vacía del estado inicial del AFN */ 3. Agregar A al conjunto Estados_de_D /* Se crea un conjunto con el elemento A */ 4. Para cada conjunto del conjunto Estados_de_D /* Se recorre ese conjunto */ 5. T = Conjunto del conjunto Estados_de_D /* Se toma un elemento */ 6. Para cada elemento del alfabeto 7. a := elemento del alfabeto 8. U = Cerradura-e (mueve(T, a)) 9. Si U no está en Estados_de_D 10. Agregar U a Estados_de_D 11. FinSi 12. Matriz_de_D[T, a] := U 13. FinPara 14. FinPara 15. Fin_del_algoritmo

Como ejercicio vamos a tomar el diagrama del autómata no determinista siguiente:

Insertar Grafica

A=Cerradura vacia de S0 A={0}

Del estado 0 solo se puede llegar a 0 sin consumir símbolos de entrada

Estados_de_D={A}

T=A={0}

a = ‘a’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(0,’a’))

U=Cerrad-vacia(1)

U={1,2,3,5,8}=B

T=A={0}

a = ‘b’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(0,’b’))

U=Cerrad-vacia(vacio)

U=vacio; no se lo considera

a b A B B

Se llena la matriz con las

entradas (A,a)=B

Estados_de_D={A, B}

T=B={1,2,3,5,8}

a = ‘a’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(1,2,3,5,8, ’a’))

U=Cerrad-vacia(4,9)

U={2,3,4,5,7,8,9}=C

T=B={1,2,3,5,8}

a = ‘b’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(1,2,3,5,8, ’b’))

U=Cerrad-vacia(6)

U={2,3,5,6,7,8}=D

a b A B B C D

Se llena la matriz con

las entradas (B,a)=C y

(B,b)=D Estados_de_D={A, B, C, D}

T=C={2,3,4,5,7,8,9}

a = ‘a’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,4,5,7,8,9, ’a’))

U=Cerrad-vacia(4,9)

U={2,3,4,5,7,8,9}=C (se repite)

T=C={2,3,4,5,7,8,9}

a = ‘b’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,4,5,7,8,9, ’b’))

U=Cerrad-vacia(6,10)

U={2,3,5,6,7,8,10}=E

a b A B B C D C C E D

Se llena la matriz con

las entradas (C,a)=C y

(C,b)=E Estados_de_D={A, B, C, D, E} T=D={2,3,5,6,7,8} T=D={2,3,5,6,7,8} a b

A B

a = ‘a’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,5,6,7,8, ’a’))

U=Cerrad-vacia(4,9)

U={2,3,4,5,7,8,9}=C (se repite)

a = ‘b’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,5,6,7,8 ’b’))

U=Cerrad-vacia(6)

U={2,3,5,6,7,8}=D (se repite)

B C D C C E D C D

Se llena la matriz con

las entradas (D,a)=C y

(D,b)=D Estados_de_D={A, B, C, D, E}

T=E={2,3,5,6,7,8,10}

a = ‘a’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,5,6,7,8,10, ’a’))

U=Cerrad-vacia(4,9)

U={2,3,4,5,7,8,9}=C (se repite)

T=E={2,3,5,6,7,8,10}

a = ‘b’

U=Cerrad-vacia(Mueve(T,a))

U=Cerrad-vacia(Mueve(2,3,5,6,7,8,10, ’b’))

U=Cerrad-vacia(6)

U={2,3,5,6,7,8}=D (se repite)

a b A B B C D C C E D C D E C D

Se llena la matriz con

las entradas (E,a)=C y

(E,b)=D

Al graficar la matriz, el autómata resultante es el siguiente:

Capitulo 2 Expresiones y Lenguajes Regulares

Conversión de una expresión regular en autómata finito

Como conclusión de lo hasta ahora visto, es posible expresar mediante una expresión regular un lenguaje regular, por lo que ahora nos vamos a centrar en un proceso de transformación de una expresión regular a un autómata finito no determinista. El algoritmo que se presenta más adelante, se basa en el orden que tiene la construcción de la expresión regular y toma cada uno de sus componentes por separado, construyendo un AFN para cada componente; estos AFN se unifican en el mismo orden en que se expresa la expresión regular, dando como resultado un AFN que reconoce el lenguaje que genera la expresión regular en cuestión.

Algoritmo de transformación de una expresión regular en un AFN

Para cada uno de los componentes sintácticos de la E-R ejecutar los pasos uno y dos

Paso uno) Para ε (vacío) construya el autómata correspondiente.

Paso dos) Para cada símbolo a independiente de la expresión regular construya su autómata correspondiente.

En los dos casos i es el estado inicial y f el estado final o de aceptación de la subexpresión.

Combinar los autómatas resultantes de acuerdo a las guías del paso tres.

Paso tres) Si Se tiene dos AFN para las expresiones s y t

a) Para la expresión s . t construya el autómata finito siguiente:

Insertar Imagen

d) Para la expresión regular (s) (entre paréntesis) utilice el AFN que diagramó para s

Ejemplo: Para la expresión regular a (a + b)* ab obtener el AFN

Paso uno y paso dos)

Las expresiones que forman parte de la expresión regular son:

1. a

2. a

3. b

4. a

5. b

Note que para cada componente se requiere un AFN independiente.

Autómata para el componente 1

Autómata para el componente 2

Autómata para el componente 3

Autómata para el componente 4

Autómata para el componente 5

Paso 3)

Combinación de los autómatas a + b

Obtención de (a U b)*

Concatenación de a con (a U b)*

Concatenación de a (a U b)* con a

Capitulo 3 Analisis Lexico

Para el desarrollo de este capitulo, no hace falta trabajar con el texto guía, trabajaremos únicamente con la guía didáctica, pero es necesario que primero lea el anexo A. Inicialmente veremos que es el análisis léxico, para lo cual es necesario comprender cual es el trabajo de un compilador y cuales son sus partes: Un compilador es un programa que convierte un programa escrito en un lenguaje de alto nivel en un programa en código objeto y luego en ejecutable. Ejemplo: Cuando usted escribe un programa en lenguaje C++, antes de hacerlo funcionar(correr) debe convertirlo en

ejecutable, para ello utiliza un compilador. El compilador se encarga de verificar que no tenga errores y luego lo convierte en ejecutable (con extensión .EXE)

El compilador cumple los siguientes tres pasos:

1. Verificación de errores del programa fuente(código de alto nivel)

Verificación de errores léxicos q Verificación de errores sintácticos q Verificación de errores semánticos

Transformación del código de alto nivel en código objeto

Transformación del código objeto en código maquina(ejecutable)

Lo anterior significa que el compilador esta formado por los siguientes módulos:

Modulo léxico.- Encargado de verificar que no existan errores léxicos Modulo sintáctico.- Encargado de verificar que no existan errores sintácticos

Modulo semántico.- Encargado de verificar que no existan errores semánticas

Modulo generador de código objeto.- Encargado de convertir el programa fuente en programa objeto(código ensamblador)

Encadenador.- Encargado de convertir el programa objeto en código o maquina programa ejecutable(unos y ceros)

Esquema de módulos de un compilador

Como conclusión podemos anotar que el analizador léxico (o modulo léxico) se encarga de verificar que todas las palabras escritas en el programa fuente pertenezcan al lenguaje de alto nivel en el que se escribe el programa. Ejemplo: Dado el programa

int main() {

   int b=10;

   cout << a+b;

   retur 0;

}

El analizador léxico debe detectar que a+b es un error léxico porque a no ha sido declarada como variable.

De igual forma en la línea “retur 0”, el analizador léxico detectará que retur no es una palabra reservada (le falta una n al final)

Ya sabemos cual es la tarea de un analizador léxico, ahora veamos cuales son sus etapas.

Una vez escrito un programa fuente, para compilarlo(transformarlo), es necesario abrirlo y empezar a leerlo, luego se deben ir concatenando (uniendo) cada uno de sus caracteres para formar cadenas y a su vez hay que comprobar que cada cadena pertenezca al lenguaje en cuestión. Suponga que el lenguaje en cuestión es C++. Entonces hay que verificar que cada una de las cadenas del programa fuente sea una palabra reservada o un identificador. Observemos el programa:

1.    int main() {

2.    int b=10;

3.    cout << a+b;

4.    return 0;

5.    }

En la línea 1 del archivo (quiero decir del programa) se van uniendo los caracteres i, n y finalmente la t para formar la cadena int (sabemos que la cadena termina en t por el espacio que le sigue “separador”) y luego hay verificar si esta cadena es una palabra reservada de C++ o es un identificador, caso contrario tendremos un error de tipo léxico. De igual manera procedemos con la cadena main, en lo que respecta a los paréntesis, el analizador debe ser lo suficientemente inteligente como para entender que son símbolos independientes de la cadena main y cuando los reconozca, debe retornar un indicador adecuado que permita saber que se reconoció un paréntesis.

Para comparar, es necesario que las palabras reservadas estén guardadas en alguna estructura, conceptualmente se maneja el termino tabla de símbolos, en ella se guardan las palabras reservadas y los identificadores(variables) que se declaran, cuando el analizador léxico forma una cadena, esta se compara con los elementos almacenados en esta tabla de símbolos. Primero se busca si es palabra reservada, si no es, se busca si es alguna variable ya declarada.

Resumiendo, podemos decir que las etapas del análisis léxico son:

Apertura del archivo. Lectura de sus caracteres.

Concatenación de caracteres.

Comparación de las cadenas que se forman con los elementos de la tabla de símbolos.

Retorno de un indicador de la cadena reconocida, también llamado token.

Especificación de componentes léxicos

Cuando se diseña un lenguaje de programación, es necesario definir cuales serán las palabras reservadas, que forma tendrán los identificadores, que formato tendrán los valores numéricos, etc. Esto depende del tipo de aplicación que se le vaya a dar al lenguaje de programación, por ejemplo si se quiere construir un lenguaje C++, será necesario incluir palabras como int, main, return, etc. Se debe definir que los identificadores inicien con una letra o con un número o con guion bajo y luego puedan contener letras o números, así mismo los valores numéricos deben iniciar con un número, luego debe n tener un punto decimal y luego pueden tener más números.

Las palabras reservadas serán fijas, pero los identificadores y valores numéricos pueden ser especificados con una expresión regular. Observe el siguiente ejemplo:

l d ¦ _ (l ¦ d ) (l ¦ d ¦ _)

Con esta expresión regular estamos indicando que los identificadores pueden iniciar con una letra o con un digito o con un guion bajo, luego deben tener una letra o un digito y después pueden tener letras, dígitos o guiones bajos.

En el caso de los valores numéricos, se puede especificar su formato con la siguiente expresión regular:

(d+.d+) ¦ (d+)

Estamos indicando que pueden empezar con uno o mas números, seguidos de un punto decimal y luego tener mas dígitos, o también pueden ser solamente números(sin punto decimal).

Recuerde que el símbolo ¦ (línea) significa o (para escoger una u otra opción).

En el siguiente cuadro se indica la diferencia entre lexema y componente léxico y token: En el siguiente cuadro se indica la diferencia entre lexema y componente léxico y token:

Lexema Componente Lexico Token Velocidad ID ID 10 NUM NUM Int int Int

Observe que el lexema es la cadena que se encuentra en el archivo fuente, el componente léxico es una clasificación a la que pertenece el lexema y finalmente el token es el valor que retorna el analizador léxico una vez que reconoció un lexema. El token también puede ser un código que el diseñador le asigne a cada componente léxico. Concluyendo, los componentes léxicos se especifican a través de expresiones regulares, las mismas que luego deben ser programadas en el analizador léxico.

Reconocimiento de componentes léxicos

Con el fin de facilitar el entendimiento, vamos a dividir el reconocimiento de componentes léxicos en categorías (esto no es normal, sin embargo es útil), las categorías en las que podemos trabajar son:

Palabras reservadas

identificadores

Valores numéricos

En todos los casos vamos a utilizar una tabla de símbolos (TDS), esta es una estructura que permite guardar información acerca de los componentes léxicos. Normalmente es una lista ligada con algunos atributos, observe la siguiente figura:

    Lista ligada que representa una tabla de simbolos

La TDS es una estructura donde normalmente están guardadas todas las palabras reservadas del lenguaje de programación que se construye. El campo com_lex es el espacio en donde se guardan todas las palabras reservadas o los identificadores que forman parte del programa, el campo valor sirve para guardar los valores que puedan ir tomando las variables y el campo tipo sirve para indicar el tipo de dato que le corresponde a cada variable. En términos generales lo que el analizador léxico hace es formar una cadena con los caracteres del programa fuente y compararla con cada una de los nodos de la estructura. Normalmente la búsqueda (para la comparación), se da a través de algún tipo de hash o utilizando en lugar de una lista ligada un árbol B, con lo que se acelera la búsqueda. Para reconocer las palabras reservadas, el diseñador del lenguaje de programación puede optar por una expresión regular como la siguiente:

letra+

Que significa que una palabra reservada puede estar formada por una o mas letras.

Esta expresión regular transformada en seudocódigo puede quedar como sigue:

Abrir archivo fuente Mientras no sea fin de archivo /*****Con las siguientes 4 líneas vamos a formar la cadena ósea la palabra reservada

Vaciar la variable c /* inicializarla con vació

Leer el siguiente carácter

Si el carácter es una letra

    Mientras el carácter es diferente de espacio

     Agregar el carácter a c /* c es una variable */

     Leer el siguiente carácter

   Fin mientras

Fin si

/*****Ahora lo vamos a buscar en la TDS

Si el valor de c se halla en la TDS

   Retornar c /* que es el token de la palabra reservada

Si no

   Retornar ID /* que es el token para un identificador

Fin si

Fin mientras

Cerrar archivo

Como recordaran, el modulo léxico reconoce cadenas y retorna el token (símbolo) que las identifica, en el seudocódigo anterior se retorna ID en el caso de las palabras reservadas y se retorna la cadena misma, es decir la palabra reservada, en este caso es igual al token.

Para reconocer identificadores, podemos utilizar la siguiente expresión regular:

Ld _ (Ld)(Ld_)

Note que el símbolo significa o

Se puede empezar con letras, dígitos o guión bajo, como segundo carácter del identificador puede ir una letra o un digito y de ahí en adelante puede ir una letra, un digito o un guión bajo. Esa expresión regular puede representarse en pseudocódigo como se muestra a continuación.

Abrir archivo fuente

Mientras no sea fin de archivo /*****Con las siguientes 4 líneas vamos a formar la cadena ósea la palabra reservada

   Vaciar la variable c /* inicializarla con vació

   Leer el siguiente carácter

   Si el carácter es una letra o un digito o un guion bajo

     Mientras el carácter es letra o es digito o es guion bajo

       Agregar el carácter a c /* c es una variable */

       Leer el siguiente carácter

     Fin mientras

   Fin si /*****Ahora lo vamos a buscar en la TDS

   Si el valor de c se halla en la TDS

     Retornar c /* que es el token de la palabra reservada

   Si no

     Retornar ID /* que es el token para un identificador

   Fin si

Fin mientras

Cerrar archivo

Con el código escrito podemos notar que no existe una forma de asegurarnos que el segundo carácter no sea un guión bajo, por lo que en ocasiones el código es algo mas difícil de implementar. Ante esto surge la necesidad de programar un autómata como veremos a continuación.

     Autómata para reconocer identificadores en C++

Observe que el reconocimiento inicia en el estado cero y desde ahí se puede leer una letra o un digito (un número) o un guión bajo, se llega al estado uno y desde ahí leyendo letra o digito se traslada al estado dos, en donde se pueden leer letras dígitos o guiones, en cualquier caso serán identificadores válidos. Este autómata se puede programar, observe el siguiente procedimiento:

Inicio

Abrir archivo

Variable estado igual cero (estado=0)

Variable c igual vacío (c=””)

Mientras no sea fin de archivo y c sea diferente de espacio

  Leer el siguiente carácter en c

   En caso de que estado

     Sea cero y c sea letra o digito o guión

       Estado es igual a uno

     Sea uno y c sea letra o digito

       Estado es igual a dos

     Sea dos y c sea letra o digito o guión

       Estado es igual a dos

     En cualquier otro caso Error léxico y terminar

   Fin de caso

Fin mientras

Retornar ID

Cerrar archivo

Fin

Es posible programar autómatas para cualquier expresión regular, sin embargo cuando se trata de lenguajes de programación complejos, podemos hallarnos con dificultades en el reconocimiento de los componentes léxicos. A continuación se presenta un algoritmo tomado del texto Compiladores técnicas y herramientas del Dr. Alfred Aho, el mismo que resume de manera sencilla los diferentes aspectos que se deben tomar en cuenta al implementar un analizador léxico.

function analex: integer;

var buflex array[0..100] of char /* arreglo de longitud 100

c char;

begin

   loop begin

     lee un carácter en c

     if c es un espacio en blanco o un símbolo tab then

       no hacer nada;

     else if c es un carácter de línea nueva then

       numlinea :=numlinea + 1;

     else if c es un digito then begin

       asignar a valcomplex el valor de este y los dígitos siguientes;

       return NUM;

     end

     else if c es una letra then begin

       poner c y las letras y dígitos sucesivos en buflex;

       buscar buflex en la TDS

       if buflex no esta en la TDS then begin

         insertar buflex en la TDS

         return ID

       end

     end

     else begin

       asignar NINGUNO a valcomplex;

       return el numero entero del carácter c;

     end

   end

end

La tarea es hacer funcionar de forma manual este algoritmo utilizando un archivo que contenga cadenas de caracteres.

Capitulo 4 Automatas a Pila

Capitulo 5 Lenguajes Independientes de Contexto

Capitulo 6 Maquinas de Turing

Construcción de máquinas de turing

A continuación se presentan ejemplos de construcción de máquinas de turing: Escriba una máquina de Turín que reconozca cadenas de unos y ceros alternados que siempre inicien en uno y siempre terminen en cero (01)+

La recomendación está en iniciar definiendo la función de trancisión, luego se pueden definir los elementos restantes de la máquina:

La maquina siempre inicia en el estado q0, y la cadena que reconoce, siempre inicia con 0:

(q0, vacio) = (q1, vacio, D) Inicio del trabajo de la máquina

(q1, 0) = (q2, 0, D)

Inicia reconociendo el cero de la cadena, lo escribe en la cinta y se mueve hacia la derecha

(q2, 1) = (q1, 1, D)

Cuando encuentra un uno, regresa al estado q1 para volver a reconocer un cero

(q1, blanco) = (q3, blanco, I)

En el estado q1 puede encontrar el símbolo en blanco que indica que la cadena se termino, en ese caso regresa una posición y se mueve al estado 3 en donde se reconoce la cadena.

Note que en el estado q1 puede reconocer un cero lo que indica que la cadena continua o puede encontrar un símbolo en blanco lo que

indica que la cadena termina

Ahora definimos los elementos restantes de la máquina:

Estados = {q0, q1, q2, q3}

Alfabeto de la cinta = {0,1, blanco}

Alfabeto = {0,1,}

Estado inicial = {q0}

Estado final = {q3}

Diseñemos ahora una máquina que acepte comentarios en lenguaje c, recuerde que los comentarios en lenguaje c son de este tipo:

/* Aquí va el comentario */

El contenido del comentario puede ser cualquier símbolo, al que llamaremos c

Este símbolo no puede ser el “*”

Igualmente definamos primero la función de transición:

(q0, vacio) = (q1, vacio, D) Inicio del trabajo de la máquina

(q0, vacio) = (q1, vacio, D) Inicio del trabajo de la máquina

(q1, /) = (q2, /, D) Inicia reconociendo el “/” de la cadena, lo escribe en la cinta y se mueve hacia la derecha

(q2, *) = (q3, *, D) Cuando encuentra un *, avanza para seguir el reconocimiento

(q3,c) = (q3, c, D) En el estado q3 puede estar leyendo muchos símbolos cualquiera a excepción del *

(q3,*) = (q4, *, D) Cuando en el estado q3 encuentra un *, se prepara para a continuación recibir un /

(q4,/) = (q5, /, D) Cuando en q4 recibe un /, se prepara para terminar de reconocer la cadena

(q5, blanco) = (q6, blanco, I)

En el estado q5 puede encontrar el símbolo en blanco que indica que la cadena se termino.

Ahora si completamos la máquina

Estados = {q0, q1, q2, q3,q4,q5,q6}

Alfabeto de la cinta = {/,*,c,blanco}

Alfabeto = {/.*,c}

Estado inicial = {q0}

Estado final = {q6} JC T/mc-16-02-07-39