Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

3

UNIVERSIDAD SALESIANADE BOLIVIA

INGENIERIA DE SISTEMAS

DOSSIER

LENGUAJES FORMALES Y COMPILADORES

Octavo Semestre

· Ing. Erlinda Elvira Gutierrez Poma

I I - 2011

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

4

UNIDAD I

PRELIMINARES MATEMÁTICOS

1. INTRODUCCIÓN

La teoría de conjuntos es una de las partes de la matemática que se desarrolló desde fines del

siglo XIX. Ha introducido términos como pertenencia, inclusión, unión y otros con significados

rigurosos y su uso sin dudas ha permitido mejorar la presición del lenguaje en áreas de

conocimiento como la teoría de relaciones y funciones, la teoría de las probabilidades y otras.

2. DEFINICIONES Y CONCEPTOS

CONJUNTO

Un conjunto es cualquier agrupación o colección de objetos o entidades o clase de objetos bien

definidos. Los conjuntos se anotan generalmente con una letra mayúscula.

ELEMENTO

Un elemento es cada uno de los objetos que forman un conjunto, se encierran entre llaves,

generalmente se usan minúsculas.

Por ejemplo, el conjunto A formado por los elementos 1, 2 y 3, se anota así:

{ }3,2,1=A

NOTACIÓN DE UN CONJUNTO

Se usan dos maneras para definir un conjunto:

a) extensión o enumeración

b) comprensión.

DEFINICION POR EXTENSION O ENUMERACIÓN

Un conjunto está definido por extensión cuando se nombran o enumeran los elementos uno a uno

Ejemplo: El conjunto M está formado por los elementos –5 y 7, y anotamos { }7;5-=M , lo

hemos definido por extensión.

DEFINICION POR COMPRENSION

Un conjunto está definido por comprensión cuando sus elementos se conocen a través de una

propiedad que les es común a ellos y sólo a ellos.

Esa propiedad suele adquirir la forma de una función proposicional que se transforma en una

proposición verdadera (V) sólo cuando a sus variables se les asignan como valores los elementos

de ese conjunto.

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

5

Ejemplo: el mismo conjunto M del caso anterior puede ser definido por comprensión así:

{ }0352/ 2 =--= xxxM

CONJUNTO VACIO

El conjunto vacío es el que no tiene elementos, simbolizado con f

CONJUNTO UNIVERSAL

El conjunto universal es el que reúne a todos los elementos de que se trata, simbolizado con U.

DIAGRAMAS DE VENN-EULER

Estos diagramas están formados por curvas que encierran a los elementos de un conjunto del cual

se necesita proponer un gráfico representativo. La letra mayúscula que lo nombra se coloca fuera

de la curva.

Ejemplo:

A

3. TEORIA Y OPERACIONES CON CONJUNTOS

3.1 LA INCLUSION

Definición: un conjunto A está incluido en otro conjunto B si, y sólo si, todos los elementos de A lo

son también de B.

Los símbolos usuales son:

· Ì (…está incluido en…)

· Ë (…no está incluido en…)

· É (…incluye a…)

Con estos símbolos, podemos enunciar la definición de inclusión así:

BxAxBA ÎÞÎÛÌo, usando el condicional contrarrecíproco (equivalente):

AXBxBA ÏÞÏÛÌ3.1.1 PROPIEDADES DE LA INCLUSIÓN:

a) Reflexiva: todo conjunto está incluido en sí mismo. AAA Ì" :b) Transitiva: CACBBA ÌÞÌÙÌ

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

6

c) El conjunto vacío está incluido en cualquier conjunto. AA Ì" f:

d) Todo conjunto está incluido en el Universal: UAA Ì" :

UA

3.2 CONJUNTOS IGUALES

Definición: ABBABA ÌÙÌÛ=3.2.1 PROPIEDADES DE LA IGUALDAD DE CONJUNTOS:

a) Reflexiva: AAA =" :b) Simétrica: ABBA =Þ=

c) Transitiva: CACBBA =Þ=Ù=

3.3 UNION DE DOS CONJUNTOS

Definición: { }BxAxxBABAC ÎÚÎ=ÈÛÈ= /

Gráficamente: UA B

BA È3.3.1 PROPIEDADES

a. Idempotencia: AAA =È

b. Conmutativa: ABBA È=È

c. Asociativa: ( ) ( )CBACBA ÈÈ=ÈÈ

3.4 INTERSECCION DE DOS CONJUNTOS

Definición: { }BxAxxBABAC ÎÙÎ=ÇÛÇ= /

Gráficamente:

UA B

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

7

AÇ B

3.4.1 PROPIEDADES:

a. Idempotencia: AAA =Ç

b. Conmutativa: ABBA Ç=Ç

c. Asociativa: ( ) ( )CBACBA ÇÇ=ÇÇ

a) AUA =Ç .

3.5 COMPLEMENTACION DE CONJUNTOS

Definición: se llama complemento de A al conjunto formado por todos los elementos de U, que no

pertenecen a A.

El complemento de A se denota con A´, o con A . Usaremos preferentemente la segunda notación.

Entonces:

{ }AxUxxA ÏÙÎ= / , o bien, { }AxxA Ï= /

En forma gráfica:

UA

A3.5.1 PROPIEDADES DE LA COMPLEMENTACIÓN:

a. Involutiva: AA =)(

b. ABBA ÌÞÌ

3.5.2 PROPIEDADES DISTRIBUTIVAS

La unión y la intersección de conjuntos se relacionan a través de dos propiedades que se enuncian

simbólicamente a continuación:

Propiedad distributiva de la unión, con respecto a la intersección

( ) ( ) ( )CBCACBA ÈÇÈ=ÈÇ

Propiedad distributiva de la intersección, con respecto a la unión

( ) ( ) ( )CBCACBA ÇÈÇ=ÇÈ

4. LEYES DE DE MORGAN

La unión y la intersección de conjuntos se relacionan con la complementación de conjuntos a

través de otras dos propiedades que se enuncian simbólicamente a continuación:

I) Primera ley de De Morgan

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

8

( ) BABA Ç=È

II) Segunda ley de De Morgan

( ) BABA È=Ç

5. DIFERENCIA DE DOS CONJUNTOS

Definición: { }BxAxxBABAC ÏÙÎ=-Û-= /

Gráficamente: U

A B

A - B

La diferencia de conjuntos no es conmutativa.

A-B ¹ B-A5.1 PROPIEDADES

a. A-B = A Ç Bb. Propiedad distributiva de la intersección con respecto a la diferencia:

( ) ( ) ( )CBCACBA Ç-Ç=Ç-

6. CONJUNTO UNIVERSAL

En toda aplicación de la teoría de conjuntos todos los conjuntos que se consideran serán muy

probablemente subconjuntos de un mismo conjunto dado. Este conjunto se llamará conjunto

universal y se denotará por U.

Ejemplo:

En geometría plana el conjunto universal es el de todos los puntos del plano.

En los estudios sobre población humana el conjunto universal es el de todas las gentes del mundo.

7. CONJUNTO POTENCIA

La f'amilia de todos los subconjuntos de un conjunto S se llama conjunto potencia de S. Denotado

por 2 S

Ejemplo:

Si M = {a, b}, entonces 2M = {{a, b}, {a}, {b}, _ }

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

9

Si un conjunto S es finito, digamos que S tenga n elementos, entonces el conjunto potencia de S

tendrá 2 n elementos, como se puede demostrar. Esta es una razón para llamar conjunto de

potencia de S la clase de los subconjuntos de S y para denotarla por 2S.

8. NOCIONES SOBRE FUNCIONES

8.1 DEFINICIÓN DE FUNCIÓN

Una relación del conjunto A con conjunto B es un subconjunto de producto cartesiano AxB

entonces F es una funcion ó aplicación de A en B si solo si F es una relacion entre A y B tal que

todo elemento de A tiene único correspondiente en B.

F = es una función

A = es el dominio de f

B = es el codominio

8.2 DOMINIO

Es el conjunto de los elementos de A que admite imagen en B.

Df = {X . A / (X, Y) . F}

8.3 CODOMINIO

Es el conjunto de elementos de B que admite una antecedente en A como:

Cof = {y . B / (x,y) . f}

f = {(1,1,), (2,4), (3,9), (4,16),.........}

9. CARDINALIDAD

La cardinalidad de un conjunto se refiere a el numero de elementos de conjunto.

a) A = { } . | A | = 0

b) B = {a, b, c, d } . | B | = 4

c) C = {a1, a2. a3.....ak} . | C | = k

Ejemplo

Cuando es cierta la siguiente igualdad?| A U B | = | A | + | B |Resp = cuando A y B son conjuntos disjuntos, es decir | A Ï B | = 0

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

10

UNIDAD II

LENGUAJES FORMALES

1. INTRODUCCION

En matemáticas, lógica e ingeniería de Sistemas, un lenguaje formal es un lenguaje cuyos

símbolos primitivos y reglas están formalmente especificados en su unión. Al conjunto de símbolos

primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama

la gramática formal o sintaxis.

2. DEFINICION

Un lenguaje es un conjunto de cadenas sobre un alfabeto específico, un lenguaje formal es idéntico

al conjunto de todas sus fórmulas bien formadas, mientras que el alfabeto debe ser un conjunto

finito y con cada fórmula bien formada debe tener una longitud también finita, un lenguaje formal

puede estar compuesto por un número infinito de fórmulas bien formadas.

Un lenguaje formal es un conjunto de cadenas de símbolos tomados de algún alfabeto. El conjunto

vació esta formado por la cadena vacía { }

{0,1} es un lenguaje infinito. Algunos elementos de este lenguaje son ε 0, 1, 00, 11, 010 y 1101011.

Una palabra v es subcadena de otra w cuando existen cadenas x ,y - posiblemente vacías tales

que xvy w

Por ejemplo, “bora ” es subcadena de “vibora ”, vacio es subcadena de toda palabra.

3. CARACTERÍSTICAS

Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por

ejemplo:

· Cadenas producidas por una gramática formal

· Cadenas producidas por una expresión regular

· Cadenas aceptadas por un autómata como una máquina de Turing.

4. ALFABETO

Es el conjunto de símbolos primitivos o vocabulario del lenguaje

5. CADENA

Una cadena o palabra está formada por un conjunto de simbolos que pertenecen a un mismo

lenguaje, la cadena mínima o nula se llama λ.

El orden de las palabras es importante de esta manera ab es diferente de ba , por lo general las

palabras se representan con las últimas letras del alfabeto, como t, u, v, w, x, y, z

Ejemplos

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

11

1) Dado el siguiente alfabeto: Σ = {a,b}

λ, a, b, ab, aaa, bbb, abba . .

2) x=abc z = dac , la concatenación será xz = abcdac

3) λ x = xλ = x = abc

6 LONGITUD DE UNA CADENA

La longitud de una cadena x, se indica con |x| y es el número de caracteres que la complementan

Ejemplo:

|λ| = 0 , |a| = 1, |abcde| = 5

7. LENGUAJE

Un lenguaje es un conjunto de cadenas de caracteres, además:

“símbolo” es un ítem elemental del vocabulario del lenguaje que se emplea para formar las

cadenas del lenguaje, que se llaman sus sentencias

• Un “alfabeto” o vocabulario, es el conjunto de todos los símbolos que forman las sentencias del

lenguaje

- Un lenguaje está formado por los siguientes elementos:

• Un diccionario: que indica los significados de la palabra del lenguaje

• Un conjunto de reglas para describir las sentencias válidas del lenguaje, este

conjunto de reglas forma la gramática del lenguaje (sintaxis y semántica)

8. MANEJO DE CADENAS Y CARACTERES

Una cadena (o palabra) es una secuencia finita de símbolos.Por ejemplo a,b,c son símbolos y abcd

es una cadena

9. CONCATENACION

Es la cadena que se for

ma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo

Si w=”banana” y z= “rama, la concatenacion de w con z es la cadena “bananarama” y se denota

como wz ó w.z

10. POTENCIA DE CADENAS

La potencia de una cadena sobre un alfabeto es dada por la notación wk que denota

concatenacion de k copias de la cadena w

Ejemplo

Si w=122sobre el alfabeto s={ 1, 2 }

w0 = λ

w1 = 122

w2 = 122122

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

12

w3 = 122122122

11. IGUALDAD DE CADENAS

Si w y z son cadenas, se dice que w es igual a z, si tienen la misma longitud y los mismos símbolos

en la misma posición , se denota w= z

12. PREFIJO

Los prefijos de una cadena estan formados por los primeros símbolos de esta. Por ejemplo la

cadena 121 sus prefijos son: λ, 1,12,121 con lo que toda la palabra puede considerarse prefijo de

si misma.

13. SUFIJOS

Estan formados por los ultimos símbolos de esta. Por ejemplo la cadena abc sus sufijos son λ, c,

bc y abc

14. SUBCADENA

Una cadena w es una subcadena de otra cadena z, si existen las cadenas x,y para las cuales z=

xwy

15. TRANSPUESTA

La inversa o transpuesta de una cadena w, es la imagen refleja de w.

Ejemplo, si w = “able” entonces su inversa es “elba”, su notación es wl

15. OPERACIONES SOBRE CADENAS

Ejemplo

1) Si A={ rojo,verde, azul } , B= { verde,violeta} y C={ rojo, amarillo ,azul, verde} determinar los

elementos de (A ½ C) x (B-C)

(A ½ C) = ={ rojo,verde, azul }

(B-C) = { violeta}

(A ½ C) x (B-C) = { (rojo, violeta), (verde, violeta),(azul,violeta)}

2) Demuestre la igualdad de A – B = A – ( B½A),utilizando los siguientes conjuntos A= { a, d,e,f,g } y

B= { d,g,h,i}

( B½A) = { d, g } A – ( B½A)= { a,e,f } A – B = { a,e,f }

Por lo tanto se demuestra A – B = A – ( B½A)

16. LENGUAJES REGULARES

Lenguaje regular es un lenguaje formal que tiene estas características:

Puede ser descrito mediante una expresión regular

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

13

Puede ser generado mediante una gramática regular Puede ser reconocido mediante un autómata

finito

Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:

Puede ser reconocido por:

· Autómata finito determinista finito (saber si una cadena de símbolos pertenece a él o no)

· Autómata finito no determinista

· Autómata de pila

· Maquina de turing

· Gramática regular (obtener todas las cadenas de símbolos que le pertenecen)

· Expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos

que le pertenecen)

Lenguajes regulares sobre un alfabeto

Un lenguaje regular sobre un alfabeto Σ dado se define recursivamente como:

· El lenguaje vacío es un lenguaje regular

· El lenguaje cadena vacía {ε} es un lenguaje regular

· Para todo símbolo a Σ {a} es un lenguaje regular

· Si A y B son lenguajes regulares entonces A U B (unión), A•B (concatenación) y A*

(clausura o estrella de Kleene) son lenguajes regulares

· Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular

· No existen más lenguajes regulares sobre Σ

Un lenguaje formal infinito puede ser regular o no regular. El lenguaje L = {an, n > 0} es regular

porque puede ser representado, por ejemplo, mediante la El lenguaje L= {an bn, n > 0} es un

lenguaje no regular dado que no es reconocido por ninguna de las formas de representación

anteriormente enumeradas.

Los lenguajes regulares son cerrados con las siguientes operaciones, de modo que si L y P son

lenguajes regulares los siguientes lenguajes también serán regulares:

· El complemento de L

· La clausura o estrella de Kleene L* de L

· El homomorfismo φ(L) de L

· La concatenación L'P de L y P

· La unión L U P de L y P

· La intersección L ∩ P de L y P

· La diferencia L \ P de L y P

· El reverso LR de L

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

14

17. LENGUAJES FINITOS

Un subconjunto especial de los lenguajes regulares es el de los lenguajes finitos, aquellos que solo

contienen un número finito de palabras. Estos son lenguajes obviamente regulares y uno podría

crear expresiones regulares que serían la unión de todas las palabras del lenguaje que definirían

dicho lenguaje.

18. EXPRESIONES REGULARES Y SUS PROPIEDADES

Las expresiones regulares es representar todos los posibles lenguajes definidos sobre un

alfabeto S, en base a una serie de lenguajes primitivos, y unos operadores de composición.

18.1 LENGUAJES PRIMITIVOS

Es el lenguaje vacío, el lenguaje formado por la palabra vacía, y los lenguajes correspondientes a

los distintos símbolos del alfabeto.

18.2 OPERADORES DE COMPOSICIÓN

La unión, la concatenación y el cierre.

Ejemplo:

1. Lenguaje formado por las cadenas que terminan en 01

{0,1}*.{01}= ({0}È{1})*.{01} ⇒ Expresión regular es (0+1)*01

2. Lenguaje formado por palabras de longitud par sobre a’s y b’s:

{aa,ab,ba,bb}*= ({aa}È{ab}È{ba}È{bb})* ⇒Expresión: (aa+ab+ba+bb)*

19. DEFINICION DE EXPRESIÓN REGULAR

Dado un alfabeto S, las expresiones regulares sobre S se definen de forma recursiva por las

siguientes reglas:

1. Las siguientes expresiones son expresiones regulares

primitivas:

· Æ

· l

· a, siendo aÎS

2. Sean a y b expresiones regulares, entonces son expresiones regulares derivadas

· a+b (unión)

· a.b (o simplemente ab) (concatenación)

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

15

· a* (cierre)

3. No hay más expresiones regulares sobre S que las construidas mediante estas reglas.

Precedencia de los operadores

1. ( )

2. * cierre

3. . concatenación

4. + unión

Ejemplo:

Algunos ejemplos de expresión regular son:

(0 + 1)*01

(aa + ab + ba + bb)*

a*(a + b)

(aa)*(bb)*b

20. LENGUAJE DESCRITO POR UNA ER

Sea r una expresión regular sobre S. El lenguaje descrito por r, L(r), se define recursivamente de

la siguiente forma:

1. Si r=Æ ⇒ L(Æ)= Æ

2. Si r=l ⇒ L(l)= {l}

3. Si R=a, aÎS ⇒ L(a)= {a}

4. Si R=a+b ⇒ L(a+b)= L(a)ÈL(b)

5. Si R=a.b ⇒ L(a.b)= L(a)L(b)

6. Si R=a* ⇒ L(a*)= L(a)*

7. Si R=(a) ⇒ L((a))= L(a)

donde a y b son expresiones regulares.

1. Si r=Æ ⇒ L(Æ)= Æ

2. Si r=l ⇒ L(l)= {l}

3. Si R=a, aÎS ⇒ L(a)= {a}

4. Si R=a+b ⇒ L(a+b)= L(a)ÈL(b)

5. Si R=a.b ⇒ L(a.b)= L(a)L(b)

6. Si R=a* ⇒ L(a*)= L(a)*

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

16

7. Si R=(a) ⇒ L((a))= L(a)

Ejemplo: Mostrar el lenguaje descrito por una ER mediante notación conjuntista:

1. L(a*(a+b)) = L(a*)L((a+b)) = L(a)*L(a+b)

= L(a)*(L(a) ÈL(b)) = {a}*({a} È{b})

= {l,a,aa,aaa,...}{a,b}

= {a,aa,...,b,ab,aab,...}

= {an|n³1}È{anb|n³0}

2. L((aa)*(bb)*b) = {a2nb2m+1|n,m³0}

3. Si S={a,b,c}, entonces L((a+b+c)*)=S*.

4. L(a*.(b+c))

5. L(0*.1.0*)

6. L((a+b+c+...+z)*.(a+b)*)

PROPIEDADES DE LAS ER

Dos expresiones regulares r1 y r2 se dicen equivalentes, r1 = r2, si describen el mismo lenguaje,

esto es, si L(r1)=L(r2).

En base a esta definición se pueden establecer las siguientes equivalencias y propiedades:

Respecto a las operaciones + y . :

1. + y . son asociativas: a+(b+g)=(a+b)+g=a+b+g y a.(b.g)=(a.b).g=a.b.g

2. + es conmutativa e idempotente: a+b=b+a y a+a=a

3. Distributividad: a.(b+g)=a.b+a.g y (a+b).g=a.g+b.g

4. Elemento neutro: a.l=l.a=a y a+Æ=Æ+a=a

5. Æ.a=a.Æ=Æ

6. Si lÎL(a), entonces a+l=a

Respecto a la operación *:

7. a*=l+a.a*

8. l*=l

9. Æ*=l

10. a*.a*=a*

11. a.a*=a*.a

12. (a*)*=a*

13. (a*+b*)*=(a*.b*)*=(a+b)*=(a*.b)*.a*

14. (a.b)*.a=a.(b.a)*

Para comprobar si dos expresiones son equivalentes se puedeintentar transformarlos mediante

estas reglas en una misma expresión.

Ejemplos:

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

17

S={a,b,c}

1. c*.c+c* = c*¿?

c*.c+c* = c*.c+c*+l (por 6)

= c.c*+c*+l (por 11)

= l+c.c*+c* (por 2)

= c*+c* (por 7)

= c* (por 2)

UNIDAD III

MAQUINAS DE ESTADOS FINITOS

1. INTRODUCCION

Un analizador léxico reconoce tokens, los autómatas finitos son las herramientas empleadas como

reconocedores de tokens,

Las maquinas de estados finitos también se denominan autómatas finitos . Un autómata finito o

máquina de estado finito es un modelo matemático de un sistema que recibe una cadena

constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el

autómata reconoce.

Un autómata finito es un reconocedor para un lenguaje, su programación es: su entrada es una

cadena x y responde “si” si x es una sentencia del lenguaje, “no” de otra manera

2. CONCEPTOS

AUTÓMATA

Un autómata es una máquina teórica que lee instrucciones en forma de símbolos y cambia de

estado según éstas.

ÁREAS DE APLICACIÓN DE LA TEORÍA DE AUTÓMATAS:

Comunicaciones, teoría de Control, Circuitos secuenciales, recocimiento de Patrones.,

compiladores.

3. CARACTERÍSTICAS DE LAS MAQUINAS ESTADOS FINITOS

Un Automata finito es similar a una maquina de estado finito sin embargo lo que caracteriza a una

de la otra es que los automatas finitos solo tienen dos estados, un estado interno y uno de rechazo.

esta formado por una quintupla <A,S,T,q0, F>. A= Simbolos de entrada S= Estados internos T= un

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

18

Subconjunto de S (Estado de Aceptacion) q0= Estado inicial F= Funcion de proximo estado F= S x

A -→ S.

4. AUTÓMATAS FINITOS

Además de notar un AF a través de su definición formal es posible representarlo a través de otras

notaciones que resultan más cómodas.

Las Expresiones regulares. Se demuestra que dado un autómata de estados finitos,

existe una expresión regular que lo representa.

Ø υ 1* υ (1* ο 0 ο 1* ο 0)*

4.1 AUTOMATAS FINITOS DETERMINISTAS

Es un modelo matemático que consiste en :

Un conjunto de estados, denominado S.

Un conjunto (alfabeto) de símbolos de entrada, denominado

Una función de transición move que mapea un par P ( s , a ) a un estado t.s y t son estados contenidos en S, a es un símbolo de entrada.

Un estado de inicio, denotado por s0.

Un conjunto de estados de aceptación (finales), denotado por F.

Además, un autómata finito determinístico AFD debe cumplir con las siguientes características :

a) No hay transiciones etiquetadas por

b) Para cada estado s y un símbolo de entrada a, existe a lo más un arco etiquetado por a saliendo

de s.

Definición. Un autómata finito determinista (AFD) es un sistema de la forma:

(E, VT, f, e0, F)

donde:

E es un conjunto finito no-vacío de elementos llamados estados

VT es un alfabeto llamado alfabeto de entrada

f es una función de un subconjunto de E x VT en E llamada función de transición

e0 es un estado especial llamado estado inicial

F es un subconjunto de E cuyos elementos se nombran estados finales

Definición. Dado un AFD (E, VT, f, e0, F) llamaremos configuración a cualquier par

ordenado de la forma:

(e , x)

tal que e . E y x . V*

T

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

19

Si e = e0 diremos que la configuración es inicial

Si e . F y x = ε diremos que la configuración es final

Definición. Dado un AFD (E, VT, f, e0, F) y dos configuraciones de la forma:

(e , x) y (e’ , y)

diremos que existe un movimiento de (e , x) a (e’ , y) y lo denotaremos por:

(e , x) |--- (e’ , y)

si x = ay, a . VT y f(e,a) = e’

Notaciones. Dadas dos configuraciones c y c’ denotaremos por:

a) c |---+ c’ si c = c1 |--- c2 |--- ...... |--- cn = c’ con n . 1

b) c |---* c’ si c |---+ c’ ó c = c’

Definición. Dado un AFD A = (E, VT, f, e0, F) definimos como el lenguaje aceptado

por A al conjunto siguiente:

L(A) = {x | x .V*

T y (e0 , x) |---* (e , ε) para algún e . F }

5. TABLAS DE TRANSICIÓN

La función de transición move es realmente una tabla de transición, donde los renglones son los

estados y

las columnas son símbolos de entrada. La construcción de la tabla de transición -función move- se

inicia identificando los

estados que tienen al menos un arco que “salga” de ellos. Para nuestro ejemplo el estado 0 (cero)

tiene un arco etiquetado por Letra que “sale” de él, y el estado 1 tiene 3 arcos: Letra, Dig y Sub.

Los estados que tengan esta característica son añadidos como los renglones en la tabla.

7. AUTÓMATAS FINITOS NO DETERMINISTAS

Un autómata finito no determinístico es un modelo matemático que consiste de :

1. Un conjunto de estados, S.

2. Un conjunto de símbolos de entrada, _ (alfabeto).

3. Una función de transición denominada move, que mapea pares, p ( s , a ) hacia un conjunto de

estados. s es un estado y a es un símbolo en la entrada.

4. Un estado de inicio denotado por s0.

5. Un conjunto de estados de aceptación, denotado por F.

7. REPRESENTACIÓN MEDIANTE GRAFOS

Además, un AFND tiene como característica que lo diferencia de un AFD, permitir el

uso de arcos etiquetados por el símbolo

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

20

8. EQUIVALENCIA ENTRE AFD Y AFND

La naturaleza de un autómata finito no determinístico, hace que la tarea de simularlo en un

programa de computadora sea muy difícil. Para un símbolo de entrada pueden existir diferentes

transiciones estado a estado, es decir, la aceptación de una cadena puede o debe, involucrar

diferentes trayectorias y todas ellas deben de probarse para saber si la cadena de entrada es o no ,

reconocida por el AFND.

Una buena estrategia es obtener el AFND que reconozca el lenguaje denotado por una expresión

regular, para luego construir un AFD a partir de un AFND. El algoritmo que construye un AFD dado

un AFND, se denomina Construcción de subgrupos. Una vez encontrado el autómata finito

determinístico, puede ser optimizado o sea, reducir el número de estados S que lo forman.

UNIDAD IV

GRAMATICAS FORMALES

1. INTRODUCCION A LAS GRAMATICAS FORMALES Y LENGUAJES REGULARES

Una gramática esta formada por la cuádrupla:

(N, T, P, S)

donde:

N: vocabulario no terminal de símbolos que nosotros introducimos como elementos auxiliares para

la definición de la gramática y que no figura en las sentencias del lenguaje

T: vocabulario terminal, todas las sentencias del lenguaje definidas por esta gramática están

formadas por los símbolos o caracteres terminales

P: es un conjunto de reglas de derivación de las cadenas de la forma: Cadena 1 > Cadena 2

S: símbolo inicial, denominado también símbolo distinguido o axioma

Una gramática describe de forma natural la estructura jerárquica de muchas construcciones de los

lenguajes de programación.

De una gramática se derivan cadenas comenzando con el símbolo inicial y reemplazando

repetidamente un no terminal por el lado derecho de una

producción para ese no terminal. Las cadenas de componentes léxicos derivadas

del símbolo inicial forman el lenguaje que define la gramática

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

21

Nota. • En una producción los elementos léxicos, como palabras clave se denominan

componentes léxicos

• Se dice que una producción es para un no terminal si el no terminal aparece en el

lado izquierdo de la producción

LENGUAJE DEFINIDO POR UNA GRAMÁTICA

L(G) representa un lenguaje L definido por una gramática G, que es un conjunto de cadenas

(palabras) de símbolos terminales (sentencias) y que se pueden derivar partiendo de S, empleando

las reglas de P.

L(G) = { x/ (S.*x) and (x . T*}

Formas sentenciales

D(G) = { α |(S.*α) and α.(NUT)*}

Derivación izquierda

Derivación realizada sustituyendo en la forma sentencial dada, la metanoción,

de “más a la izquierda” por alguna de sus partes derechas que la definen

Derivación izquierdaCuando las derivaciones que se realizan en la forma sentencial son siempre

en la metanoción de “más a la derecha”

2. GRAMATICAS REGULARES Y AUTOMATAS

- Los elementos T o “vocabulario terminal” pueden ser:

- letras minúsculas del comienzo del abecedario

a) operadores

b) caracteres especiales

c) dígitos numéricos

d) palabras reservadas de un lenguaje de programación

- Los elementos de N o “vocabulario no terminal” pueden ser: 32

a) letras mayúsculas del comienzo del alfabeto

b) nombres en minúscula

c) También se acepta la notación BNF para escribir el nombre de la metanoción

entre paréntesis angulares.

d) El axioma o símbolo inicial

- El alfabeto Σ = NUT comprende terminales y no terminales

- Las “cadenas” de caracteres que tienen símbolos terminales y no terminales

(.(NUT)*) se escriben con letras minúsculas del alfabeto griego. Por ejemplo:

A > α

- Se indica la cadena nula con λ

3. JERARQUIA DE GRAMATICAS

Según Chomsky tenemos las siguientes jerarquia

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

22

Tipo 0: o gramática con estructura de frase, esta gramática se caracteriza por que las

producciones presentan la forma:

α>β donde α . (NUT)+ β . (NUT)*

es decir que la parte izquierda de una producción (regla) puede ser una tira de símbolos

cualesquiera de N y T pero la parte derecha puede ser además nula.

Tipo 1: o gramática sensible al contexto. Donde P presenta la forma:

αAβ>αγβ donde A . N, α y β. (NUT)* γ . (NUT)+

esta gramática se denomina sensible al contexto por que A cambia por gamma, pero solo en el

contexto formado por alfa . . . beta

Tipo2: o gramática libre de contexto. Donde la forma de P es: A>α donde A . N y α . (NUT)*

Tipo 3: o gramáticas regulares. Donde P presenta una de las dos formas siguientes:

A > aB

A > a

En estos tipos de gramáticas, cada una de ellas es más restringida que la anterior, es decir

comprende un número menor de lenguajes. La inclusión de una gramática en otra es propia, o sea

hay como mínimo un lenguaje que pertenece a una de ellas y no a su restringida.

4. GRAMATICAS INDEPENDIENTES DEL CONTEXTO

DERIVACION

En G, se dice que la tira alfa “produce directamente” la tira beta, lo que se representa α.β si se

puede escribir:

α = δ A µ β = δ γ µ

para alguna cadena delta, mu (que pueden ser nulas) y además existe una regla de

P que sea A > γ

Aplicando repetidamente la regla de derivación directa:

α = γ0 . γ1 . γ2 . γ3 . . . . . γn = β para n>0

lo cual se representa abreviadamente:

a) α.+β

b) α.*β

5. AUTÓMATAS DE PILA

Un autómata de pila o autómata apilador es un modelo matemático de un sistema que recibe una

cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje

que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de los

lenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

EJEMPLOS

Formalmente, un autómata con pila puede ser descrito como una séptupla M = (S,Σ,Γ,δ,s,Z,F)

donde:

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

23

* Σ y Γ son alfabetos de entrada, de la cadena y de la pila respectivamente;

* S un conjunto de estados;

* \delta: S \times (\Sigma \cup \{\epsilon \} ) \times \Gamma \rightarrow \mathcal{P} ( S \times

\Gamma^*) * s \in S es el estado inicial; * Z\ \in \Gamma es el símbolo inicial de la pila; * F

\subseteq S es un conjunto de estados de aceptación o finales.

La interpretación de \delta (s, a, Z) = \{ (s_1, \gamma_1), (s_2, \gamma_2), \ldots, (s_n, \gamma_n)

\}, con s, p_i \in Q, a \in (\Sigma \cup \{ \epsilon \} ), \gamma_i \in \Gamma es la siguiente:

Cuando el estado del autómata es s, el símbolo que la cabeza lectora está inspeccionando enese momento es a, y en la cima de la pila nos encontramos el símbolo Z, se realizan lassiguientes acciones: * Si a \in \Sigma, es decir no es la palabra vacía, se avanza una posición la cabeza lectora para

inspeccionar el siguiente símbolo.

* Se elimina el símbolo Z de la pila del autómata.

* Se selecciona un par (pi,γi) de entre los existentes en la definición de δ(s,A,Z), la función de

transición del autómata.

* Se apila la cadena \gamma_i = A_1 A_2 \ldots A_k en la pila del autómata, quedando el

símbolo A1 en la cima de la pila.

UNIDAD V

COMPILADORES

1. INTRODUCCION

Un compilador es un programa informático que traduce un programa escrito en un lenguaje de

programación a otro lenguaje de programación, generando un programa equivalente que la

máquina será capaz de interpretar. Usualmente el segundo lenguaje es lenguaje de máquina, pero

también puede ser simplemente texto. Este proceso de traducción se conoce como compilación.

2. CONCEPTOS Y CARACTERÍSTICAS DE LOS COMPILADORES

COMPILADOR

Un compilador es un programa que permite traducir el código fuente de un programa en lenguaje

de alto nivel, a otro lenguaje de nivel inferior (lenguaje de máquina). De esta manera un

programador puede diseñar un programa en un lenguaje mucho más cercano a como piensa un

ser humano, para luego compilarlo a un programa más manejable por una computadora.

La construcción de un compilador involucra la división del proceso en una serie de fases que

variará con su complejidad.

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

24

3. HISTORIA DE LOS COMPILADORES

El primer compilador fue escrito por Grace Hopper, en 1952 para un lenguaje de programación , En

1950 John Backus dirigió una investigación en IBM sobre un lenguaje algebraico. En 1954 se

empezó a desarrollar un lenguaje que permitía escribir fórmulas matemáticas de manera traducible

por un ordenador; le llamaron FORTRAN (FORmulae TRANslator). Fue el primer lenguaje de alto

nivel y se introdujo en 1957 para el uso de la computadora IBM modelo 704.

Surgió así por primera vez el concepto de un traductor como un programa que traducía un lenguaje

a otro lenguaje. En el caso particular de que el lenguaje a traducir es un lenguaje de alto nivel y el

lenguaje traducido de bajo nivel, se emplea el término compilador.

El primer compilador de FORTRAN tardó 18 años-persona en realizarse y era muy sencillo. Este

desarrollo de FORTRAN estaba muy influenciado por la máquina objeto en la que iba a ser

implementado. Como un ejemplo de ello tenemos el hecho de que los espacios en blanco fuesen

ignorados, debido a que el periférico que se utilizaba como entrada de programas (una lectora de

tarjetas perforadas) no contaba correctamente los espacios en blanco.

El primer compilador autocontenido, es decir, capaz de compilar su propio código fuente fue el

creado para Lisp por Hart y Levin en el MIT en 1962. Desde 1970 se ha convertido en una práctica

común escribir el compilador en el mismo lenguaje que este compila, aunque Pascal y C han sido

alternativas muy usadas.

Crear un compilador autocontenido genera un problema llamado bootstrapping, es decir el primer

compilador creado para un lenguaje tiene que o bien ser compilado por un compilador escrito en

otro lenguaje o bien compilado al ejecutar el compilador en un intérprete.

4. TIPOS DE COMPILADORES

§ Compiladores cruzados: generan código para un sistema distinto del que están

funcionando.

§ Compiladores optimizadores: realizan cambios en el código para mejorar su eficiencia,

pero manteniendo la funcionalidad del programa original.

§ Compiladores de una sola pasada: generan el código máquina a partir de una única

lectura del código fuente.

§ Compiladores de varias pasadas: necesitan leer el código fuente varias veces antes de

poder producir el código máquina.

§ Compiladores JIT (Just In Time): forman parte de un intérprete y compilan partes del

código según se necesitan.

4. FASES DEL COMPILADOR

El proceso de traducción se compone internamente de varias fases, que realizan distintas

operaciones lógicas. Es útil pensar en estas fases como en piezas separadas dentro del traductor,

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

25

y pueden en realidad escribirse como operaciones codificadas separadamente aunque en la

práctica a menudo se integren juntas.

- Fase de análisis- Análisis léxico

ANÁLISIS

Se trata de la comprobación de la corrección del programa fuente, e incluye las fases

correspondientes al Análisis Léxico (que consiste en la descomposición del programa fuente en

componentes léxicos), Análisis Sintáctico (agrupación de los componentes léxicos en frases

gramaticales ) y Análisis Semántico (comprobación de la validez semántica de las sentencias

aceptadas en la fase de Análisis Sintáctico).

Síntesis: Su objetivo es la generación de la salida expresada en el lenguaje objeto y suele estar

formado por una o varias combinaciones de fases de Generación de Código (normalmente se trata

de código intermedio o de código objeto) y de Optimización de Código (en las que se busca

obtener un código lo más eficiente posible).

Alternativamente, las fases descritas para las tareas de análisis y síntesis se pueden agrupar en

Front-end y Back-end:

§ Front-end: es la parte que analiza el código fuente, comprueba su validez, genera el árbol

de derivación y rellena los valores de la tabla de símbolos. Esta parte suele ser independiente

de la plataforma o sistema para el cual se vaya a compilar, y está compuesta por las fases

comprendidas entre el Análisis Léxico y la Generación de Código Intermedio.

§ Back-end: es la parte que genera el código máquina, específico de una plataforma, a partir

de los resultados de la fase de análisis, realizada por el Front End.

Esta división permite que el mismo Back End se utilice para generar el código máquina de

varios lenguajes de programación distintos y que el mismo Front End que sirve para analizar el

código fuente de un lenguaje de programación concreto sirva para generar código máquina en

varias plataformas distintas. Suele incluir la generación y optimización del código dependiente de la

máquina.

El código que genera el Back End normalmente no se puede ejecutar directamente, sino que

necesita ser enlazado por un programa enlazador(linker)

5. ANÁLISIS LÉXICO

El análisis léxico constituye la primera fase, aquí se lee el programa fuente de izquierda a derecha

y se agrupa en componentes léxicos(tokens), que son secuencias de caracteres que tienen un

significado. Además, todos los espacios en blanco, líneas en blanco, comentarios y demás

información innecesaria se elimina del programa fuente. También se comprueba que los símbolos

del lenguaje (palabras clave,operadores,...) se han escrito correctamente.

Como la tarea que realiza el analizador léxico es un caso especial de coincidencia de patrones, se

necesitan los métodos de especificación y reconocimiento de patrones, se usan principalmente

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

26

los autómatas finitos que acepten expresiones regulares. Sin embargo, un analizador léxico

también es la parte del traductor que maneja la entrada del código fuente, y puesto que esta

entrada a menudo involucra un importante gasto de tiempo, el analizador léxico debe funcionar de

manera tan eficiente como sea posible.

6. ANÁLISIS SINTACTICO

En esta fase los caracteres o componentes léxicos se agrupan jerárquicamente en frases

gramaticales que el compilador utiliza para sintetizar la salida. Se comprueba si lo obtenido de la

fase anterior es sintácticamente correcto (obedece a la gramática del lenguaje). Por lo general, las

frases gramaticales del programa fuente se representan mediante un árbol de análisis sintáctico.

La estructura jerárquica de un programa normalmente se expresa utilizando reglas recursivas. Por

ejemplo, se pueden dar las siguientes reglas como parte de la definición de expresiones:

1. Cualquier identificador es una expresión.

2. Cualquier número es una expresión.

3. Si expresión1 y expresión2 son expresiones, entonces también lo son:

§ expresión1 + expresión2

§ expresión1 * expresión2

§ ( expresión1 )

Las reglas 1 y 2 son reglas básicas (no recursivas), en tanto que la regla 3 define expresiones en

función de operadores aplicados a otras expresiones.

La división entre análisis léxico y análisis sintáctico es algo arbitraria. Un factor para determinar la

división es si una construcción del lenguaje fuente es inherentemente recursiva o no. Las

construcciones léxicas no requieren recursión, mientras que las construcciones sintácticas suelen

requerirla. No se requiere recursión para reconocer los identificadores, que suelen ser cadenas de

letras y dígitos que comienzan con una letra. Normalmente, se reconocen los identificadores por el

simple examen del flujo de entrada, esperando hasta encontrar un carácter que no sea ni letra ni

dígito, y agrupando después todas las letras y dígitos encontrados hasta ese punto en un

componente léxico llamadoidentificador. Por otra parte, esta clase de análisis no es

suficientemente poderoso para analizar expresiones o proposiciones. Por ejemplo, no podemos

emparejar de manera apropiada los paréntesis de las expresiones, o las palabras begin y end en

proposiciones sin imponer alguna clase de estructura jerárquica o de anidamiento a la entrada.

7. OPTIMIZACION Y GENERACIÓN DE CODIGO

La fase de optimización de código consiste en mejorar el código intermedio, de modo que resulte

un código máquina más rápido de ejecutar. Esta fase de la etapa de síntesis es posible sobre todo

si el traductor es un compilador (difícilmente un interprete puede optimizar el código objeto). Hay

mucha variación en la cantidad de optimización de código que ejecutan los distintos compiladores.

En los que hacen mucha optimización, llamados "compiladores optimizadores", una parte

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

27

significativa del tiempo del compilador se ocupa en esta fase. Sin embargo, hay optimizaciones

sencillas que mejoran sensiblemente el tiempo de ejecución del programa objeto sin retardar

demasiado la compilación.

UNIDAD VI

APLICACIÓN DE LENGUAJES FORMALES

1. INTRODUCCION

Lenguaje es un conjunto de oraciones basadas en una gramática, que a su vez se basa en un

alfabeto; un lenguaje es generalmente infinito y se forma con distintas combinaciones de palabras.

Es necesario que estas combinaciones sean bien formadas, es decir, correctas basadas en una

sintaxis y una semántica propia del lenguaje. Un lenguaje generalmente nos sirve para poder

expresar pensamientos ideas y de esta forma poder comunicarnos con las demás personas.

2. CARACTERÍSTICAS Y CONCEPTOS DE LA APLICACIÓN DE LENGUAJES FORMALES

Los lenguajes se clasifican en: naturales o formales.

2.1 LENGUAJES NATURALES

Son aquellos lenguajes que se han desarrollado y organizado gracias a la experiencia humana;

generalmente usamos los lenguajes naturales para comunicarnos con los demás, para analizar

distintas situaciones y razonar sobre las mismas, tienen un gran poder expresivo y por consiguiente

son polisemánticos, es decir, una misma expresión puede tener distintos significados dependiendo

del contexto.

2.2 CARACTERÍSTICAS DE LOS LENGUAJES NATURALES

- Son espontáneos, se han desarrollado progresivamente, enriqueciendose gracias a la

experiencia humana

- Son polisemánticos gracias a la riqueza de componentes y a la variedad de sus

expresiones

- No pueden ser formalizados completamente, precisamente por ser polisemánticos.

3. LENGUAJES FORMALES

Son lenguajes que el hombre ha desarrollado de manera objetiva para expresar y almacenarconocimiento científico. Cada palabra y oración está perfectamente definido porque tieneun solo significado que no depende del contexto.

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

28

Los lenguajes formales pueden ser usados en cualquier área de investigación para describir de

manera precisa y concisa hechos y acontecimientos libres de toda ambigüedad.

3.1 CARACTERÍSTICAS DE LOS LENGUAJES FORMALES

- Se desarrollan basados en una teoría previamente establecida

- Tienen pocos componentes semánticos que pueden ser incrementados de acuerdo con la teoría

que se desea formalizar.

- No producen oraciones ambiguas gracias a que no son poli semánticos

- Los números son muy importantes en todo lenguaje formal

- Se pueden formalizar completamente

4. LENGUAJE DE PROGRAMACIÓN

Es una combinación de un lenguaje natural y de un lenguaje formal, para poder escribirprogramas que pueden ser entendidos y ejecutados por un computador. Está compuesto pordos elementos importantes.Sintaxis. Cada sentencia de un programa debe ser escrito correctamente

Semántica. Cada sentencia de un programa debe tener un significado correcto y único.

4.1 GENERACIONES DE LOS LENGUAJES DE PROGRAMACIÓN.

Desde la aparición de las computadoras, los lenguajes de programación han idoevolucionando, distinguiéndose cinco generaciones de lenguajes de programación.

PRIMERA GENERACIÓN

Son conocidos como los lenguajes máquina basados en el sistema de numeración binario,en el que se utiliza solamente unos y ceros para comunicarse con la computadora,programar en esta generación era muy complicado, porque no se podían expresarprogramas complejos. Actualmente son muy poco utilizados, muy necesarios para laprogramación de chips.

SEGUNDA GENERACIÓN

En esta generación surgen los lenguajes ensambladores, se basan en el uso de acrónimos, que se

resumen de varias palabras en una sola. Por ejemplo la sentencia ADC que significa "ADd with

Carry", en español "sumar con acarreo".

TERCERA GENERACIÓN

En esta generación surgen los llamados lenguajes de alto nivel, los más representativos son: el C,

Pascal, Basic, Cobol, Fortran. Se asemejan más a lenguaje humano, usando palabras completas

del inglés para escribir programas. Por ejemplo writeln("Hola Mundo"), que significa imprimir en

una línea nueva "Hola Mundo".

Universidad Salesiana de Bolivia Lenguajes Formales y CompiladoresIngeniería de Sistemas

29

CUARTA GENERACIÓN

En esta generación surgen los lenguajes visuales, que cuentan con asistentes llamados Wizards

para facilitar el diseño y la implementación de los programas. Se asemejan mucho más lenguaje

humano, utilizando incluso frases de lenguaje natural, los más representativos son:Visual Basic,

Visual C, Visual Java.

QUINTA GENERACIÓN

En esta generación los programadores ya no programan, ya no se preocupan sobre cómo están

implementados los programas; simplemente se dedican a ingresar datos y hacer consultas y el

computador responde a los mismos

5. LA MAQUINA DE TURING

Las máquinas de Turing son una buena formalización del concepto de algoritmo, porque cada

programa de una maquina de Turing puede ser implementado eficientemente

Tesis de Church: Algoritmo = Maquina de Turing.

Al comenzar a funcionar, la maquina se encuentra en el estado q0 y su cabeza lectora esta en la

posición 1 de la cinta, en cada instante la máquina se encuentra en un estado q y su cabeza

lectora está en una posición p.

Si el simbolo en la posición p es a y _(q, a) = (q0, b,X), entonces:

La máquina escribe el simbolo b en la posición p de la cinta.

Cambia de estado desde q a q0.

Mueve la cabeza lectora a la posición p - 1 si X = I , y a la posición p + 1 si X = D. Si X = N,

entonces la cabeza lectora permanece en la posición p.

Los estados de F son utilizados como estados de aceptación.

Una palabra w es aceptada por una máquina M si y solo si la ejecución de M con entrada w se

detiene en un estado de F.