Tarea 2 Teoria de La Computacion Andres Ferrada Lagos

7/25/2019 Tarea 2 Teoria de La Computacion Andres Ferrada Lagos

1/18

CC3102Teora de la computacin

Tarea

Tarea 2 Autmata apilador, gramticas y

mquinas de Turing

Profesor de Ctedra: Alejandro Hevia

Auxiliares: Ivana Hachmann

Pablo Muoz Fuentes

Alumno: Andrs Sebastin Ferrada Lagos

Fecha: 13/11/2015


2/18


2

1

Entregue diagramas de estado descripcin

intuitiva de los siguientes lenguajes.

1.1Letra a

L = {x#x# . . .#x | k 1, cada xi {a, b}, y existen i, j tales que x = x}

Respecto al diseo de este autmata apilador me base en el no determinismo adems de

separar el problema en una serie de pequeos problemas. Si resulta que para algn i,j se tiene quex = x

necesito alguna forma de elegir este x y algn x entonces lo que hago es adivinar que palabrausar. Esto se logra mediante saltar una cantidad no determinista de #. Luego de posicionarme al inicio

de una palabra la copio entera en el stack, es decir copia hasta encontrar el siguiente asterisco. Ahora

otra vez debo elegir un salto no determinista de # que me llevara a otra palabra cualquiera. Por ultimo

voy comparando si la palabra que tengo en el stack es igual a la palabra que me posicione. Debido a

que es un stack la palabra se encuentra almacenada en reversa (el primer elemento que sacare ser el

ltimo que deposite) por lo que la comparacin cumple con el lenguaje.

Si se cumple todo el camino anterior para alguna combinacin de palabras tengo que la palabra

est en el lenguaje. Dada esta formulacin tengo el siguiente autmata de pila.

**Nota se ha omitido el estado donde coloca el carcter de chequeo de fin de stack. Es decir

falta un estado al inicio que no toma input, no toma stack y coloca el carcter Z ($ para la notacin vista

en clases). Ya que se puede observar que el ultimo nodo comprueba que se acabe el stack sacando este

smbolo del stack.


3/18


3

En el diagrama se puede observar los bloques que constituyen el autmata. Los bloques rojos

como explique saltan una cantidad no determinista de # lo que permite revisar todos las palabras. El

bloque azul guarda el string de la palabra entre el # seleccionado y el siguiente. El bloque verde permite

comprobar que la palabra sea el reverso. Por ltimo el estado siguiente se encargar de procesar la

entrada restante con tal de aceptar (recordar que se requiere vaciar entrada).

Ilustracin 1 Autmata que reconoce lenguaje 1 por bloques. Bloques rojos saltan una cantidad de # (0 a n) azul agrega palabra, verde

revisa reverso

Posteriormente me di cuenta del caso de borde i = j en tal caso podemos hacer un salto no determinista

entre guardar la palabra y revisarla.


4/18


4

1.2

Letra b

L2 = { w {a, b} | ||w||a = 2 ||w||b }, donde ||w||x es el nmero de veces que aparece elsmbolo x {a, b} en w.

En este caso me base en el autmata que s que cuenta el mismo nmero de as que de bs .

Este autmata es el siguiente.

Ilustracin 2 autmata que reconoce palabra con misma cantidad de a's que de b's


5/18


5

Aqu la clave para que este lenguaje sea reconocido por este autmata es el no determinismo y que el

conteo se represente con dos smbolos. De lo contrario dependiendo del orden de la palabra (van

primero las a o las b) fallara. Sin embargo el no determinismo adivina el camino correcto.

En el problema actual se pide que se reconozca palabras con 2 veces ms b's que a's para esto debo

modificar algo las reglas que maneja la letra a. Debo colocar que para cada a que observe o se colocan

dos caracteres X o si exista un carcter Y en pila colocar solamente una X (ya que con dos b's se

neutraliza a un a si llevo uno solo me falta otra b).

De esta forma podre otra vez utilizar el no determinismo para solucionar el problema ya que se elige el

camino valido (que sabemos que existe ya que podramos nosotros tomar las reglas correctas en cada

paso y tener el resultado).

Ilustracin 3 autmata que reconoce palabras con doble cantidad de b que de a


6/18


6

2

Demostrar que los siguientes lenguajes no son

gramticas de libre contexto.

2.1Letra a

L3 es el conjunto de las cadenas formadas por smbolos a,b y c con la misma cantidad de a,b y c

Primero enunciamos el lema de bombeo el cual utilizaremos para la demostracin (contra

reciproca del lema).

Un lenguaje no es una gramtica libre de contexto si se cumple lo siguiente

, , ||

Tal que = alguna de las siguientes condiciones falla

1. 0, 2. 13.

En todas las demostraciones a continuacin se asumen la segunda y tercera para demostrar que

la primera no se puede satisfacer.

Para esta demostracin utilizare la palabra = claramente la palabra essuficientemente grande 3 veces ms grande. S pertenece al lenguaje al poseer mismo nmero de a,b,c.

Para conseguir todas las particiones de la palabra se analizan los siguientes casos. Tambin se

asumen la condicin 2,3.

Caso contiene solo un tipo de carcter: Es decir estn en una de estas secciones enla izquierda (caracteres a) al medio (caracteres b) o a la derecha (caracteres c). En tal

caso se tiene que va generar al menos un carcter ms en alguno de esassecciones (al menos uno ya que > 1) como se genera en solo una seccin lasotras dos secciones no tendrn como igualar la cantidad de caracteres y la palabra

bombeada se sale del lenguaje.


7/18


7

Caso est en alguna de las fronteras entre secciones (entre a,b o entre b,c). Primeroque nada la condicin 3 nos da una limitacin es decir no podemos colocar la parte que

se bombea en ms de 2 secciones ya que la palabra no puede ser ms grande que p y

para colocarlo en 2 fronteras requiero palabras de al menos p + 2. Ahora si esta en alguna

interseccin tenemos dos casos uno la cantidad de bombeo esta equilibrada para ambas

fronteras (estoy en frontera a,b y bombeo misma cantidad de as que de bs) en este

caso al bombear rompo la igualdad respecto a la cantidad de cs (o sea cual sea el

carcter que no esta en este frontera). Por ultimo si no llegaran a estar equilibrado

simplemente al bombear rompo la simetra.

En cualquier caso la idea es que no puedo bombear sin que solo bombee a lo ms dos caracteres

distintos por lo que al bombear para 2las palabras se salen del lenguaje y por lo tanto el lenguajeno era libre de contexto.

2.2Letra b

4 = {| 2}

Utilizando el lema de bombeo elijo la siguiente palabra =

Los casos son los siguientes:

est en la seccin de solo as. Si esta en esta seccin bombearlo con 2genera que lacantidad de as supere a las cantidad de bs por lo que no est en el lenguaje.

est en la seccin de solo bs. Si esta ac similarmente a la anterior bombearlo la cantidadde as , bs no ser la misma.

est en la seccin de solo cs. Si esta ac con 2tendremos al menos m + 1 cs lo que

significa en este caso 2p + 1 lo cual es mayor que 2p por lo que no est en el lenguaje. esta en la frontera a,b. Ac hay dos casos.

o Se eligen la cantidad de a,b en el bombeo de forma asimtrica al bombear serompe la igualdad de a,n. 2

o Se eligen la cantidad de a,b en el bombeo de forma simtrica. En tal caso elproblema es que se debe mantener la condicin entonces (+

) tendr

que = 2 1 > = 2 tendr una cantidad al menos superior (esto se tiene yaque se bombea al menos 2 por bombeo al ser > 1y la cantidad es simtrica


8/18


8

por lo que en la iteracin (+

) estoy seguro que es mayor ). Como es mayor se sale dellenguaje.

esta en la frontera b,c. Sea como lo bombee cambiare la cantidad de bs sin cambiar la

cantidad de as por lo que esta fuera del lenguaje.

Tambin hay que recordar que estos son todos los casos posibles ya que entonces laparte bombeada no se puede colocar entre ms de dos fronteras.

3Describir gramtica y convertir a forma normal

de Chomsky

G: S XY , X aXb |, Y bY a | .

La primera regla S XYquiere decir que hay una concatenacin entre la gramtica que describe

la variable inicial X y la gramtica que describe la variable inicial Y

X aXb | es un regla que permite crear siempre un numero simtricode a,b en ese orden.

Formando el patrn 0 La regla Y es simtrica pero cambia el orden a 0 Es importante notar que n, l son independientes entre si.

Entonces algunas formas de mayor nivel para expresar el lenguaje serian:

L = { + , 0}

L = { 0}

L = {Concadenar la misma cantidad de as unidos a la misma cantidad de bs unidos con otra palabra

que posea la misma cantidad de bs unidos con as}


9/18


9

Ahora para convertir a la forma normal de Chomsky se deben tener lo siguiente

Toda regla posee la forma

A BC (donde B, C no son variables iniciales)

A a (donde a no es el carcter vaco e)

Se permiten S e

El proceso a realizar es el siguiente:

1. Si la variable inicial aparece en algn momento a la derecha crear una nueva variable inicial que

apunte a la antigua

2. Eliminar las reglas A e. Remplazando en todas las reglas que apuntaban a A el carcter vaco.3. Borrar todas las reglas del tipo A B y remplazar por los terminales que tena B.

4. Si A abc partir de a dos en variables que llevan a terminarles. Por ejemplo Si A A1A2 , A1

a, A2 A3 A4, A3 b, A4 c

Entonces vamos regla por regla hasta convertir todas en reglas vlidas.

S XY es vlida ya que son dos variables no iniciales

X no es vlida entonces la eliminamos y se generan las nuevas reglas X ab, S Y.

Y no es vlida entonces la eliminamos y se generan las nuevas reglas y ba, S X. Adems

de la regla S Y ahora indica S(la cual es vlida por ser S variable inicial).

Despus de dichos pasos la gramtica queda.

S XY | X | Y |

X ab | aXb

Y ba | bYa

An quedan reglas invalidas continuamos

Para los terminales creare las variables A a, B b.

Entonces para que las variables de X cumplan con tener dos variables a la derecha. Modifico sus

variables que ahora sern X AX1, X AB. Donde X1 XB.

Las variables de Y siguen un proceso similar Y BA, Y BY1. Donde Y1 YA

Quedan las siguientes variables


10/18


10

S XY | X | Y |

X AX1 | AB

Y BY1 | BA

X1 XB

Y1 YA

Solo queda eliminar la variables unarias en S. Donde se deben remplazar por las reglas validas en tanto

X como en Y. El resultado es el siguiente.

S XY | AX1 | AB | BY1 | BA |

X AX1 | AB

Y BY1 | BA

X1 XB

Y1 YA

Con lo cual tenemos una gramtica equivalente a la inicial con forma normal de Chomsky.

4Formule la definicin formal de autmata de

cola y demuestre que es equivalente a una

mquina de Turing


11/18


11

Para lograr esto me base en el comportamiento de un numero al ir ingresando valores y el

modulo del nmero que queremos buscar mltiplos. Por ejemplo para el caso m = 3.

Como m = 3 los valores de su mdulo estn entre 0, 1,2 siendo 0 el valor que nos gustara que

fuese para aceptarlo.

5

De descripciones de mquinas de Turing bajo y

alto nivel de las siguientes lenguajes

5.1Parte a

3 = { m(,), 0}

Para reconocer este lenguaje la nica dificultad se encuentra en como determinar el mnimo

entre m,n y probarlo ya que comprobar que una palabra tenga misma cantidad de letras es fcil.

Para resolver el problema pens en lo siguiente. Si yo tengo las as, las bs y las cs ordenadas y

voy comparando una a una las letras. De ser c igual al mnimo entre la cantidad de a s y bs deben

terminarse las a junto con las c de ser la cantidad de as mnima o terminarse las bs con las c.

Entonces el diagrama de alto nivel es el siguiente. Utilizare una maquina de Turing de 3 cintas.

Primero marcare en las 3 cintas el primer carcter

Luego separare la entrada (escrita en la primera cinta) dejando todas las as en la primera

cinta, todas las bs en la segunda cinta y todas las cs en la tercera cinta.

Rebobinar la primera cinta hasta encontrar el primer carcter

Rebobinar la segunda cinta hasta encontrar el primer carcter

Rebobinar la tercera cinta hasta encontrar el primer carcter

Si en las 3 cintas hay caracteres avanzar, si se acaban todas a la vez acepta. Si se acaba

la de las c y la de las a acepta. Si se acaba la de las b y las c acepta. En todos los dems

casos rechaza.


12/18


12

El diagrama de estados general de la maquina es el siguiente.

Convenciones y notacin:

En esta ocasin se ha utilizado el carcter cuadrado como el carcter vacio para la cinta.

La funcin transicin se define (a,b,(D,I,S)) donde lee el carcter a coloca el carcter b en dicha

posicin y se mueve a derecha, izquierda o se mantiene segn corresponda. La transicin entre

estados se musetra mediante una flecha direccional que indica el estado antes de la transicin

y el despus de esta.

Al ser multicinta (3 en este caso) se anotan una tupla de 3 elementos (a,b,(D,I,S)) | (a,b,(D,I,S))

| (a,b,(D,I,S)) que representa que leer escribir en cada cinta. Es necesario que coincidan las

especificaciones de lectura de las 3 cintas para tomar dicha transicin.

Toda transicin no sealada lleva al estado de rechazo.

Ilustracin 4 Diagrama maquina de turim que reconoce L3 por bloques

En este diagrama en rojo la seccin que permite marcar los caracteres iniciales en las 3 cintas. Ennaranjo esta la seccin que escribe todas las as en la primera cinta, todas las bs en la segunda cinta y

todas las cs en la tercera cinta. En verde la seccin que rebobina las 3 cintas a su smbolo inicial. Por

ltimo la parte azul comprueba que se acaban las cs con el mnimo entre m,n.

5.1.1 Explicacion por secciones


13/18


13

5.1.2 Bloque de entrada (en rojo)

Re ordenando un poco para verlo mejor el bloque de entrada es lo siguiente:

Ilustracin 5 Bloque de entrada

Lo primero que hace es llegar al final de la entrada. Ac vemos que escribe el mismocarcter que lee de forma de no alterar el input. Cuando lleguemos al final de la entrada

encontraremos cuadrados escritos en las 3 cintas en tal caso retrocedemos la cinta con

el input y pasamos al estado q6. Es importante notar que si bien movemos las dems

cintas el movimiento de estas por el momento no tiene importancia.

En el estado q6 reviso que es lo que est escrito en el ltimo carcter revisado. Esto nos

lleva por 3 caminos al ser posibles solo 3 caracteres. Siempre colocas una X en donde

estaba anteriormente el carcter y avanzas. En el espacio siguiente donde antes estaba

vacio vamos a escribir el carcter que remplazamos por X. Y luego volvemos a donde

escribimos X quedando en el estado q9.

o

En resumen realizamos (.char ) (.X ) (.X char) El siguiente paso es determinar si llegamos al inicio de la cinta, si vemos algn carcter

a,b,c es que debemos repetir el proceso. La condicin de termino es dependiente de la

implementacin. En la implementacin que se utiliz la cinta de la mquina de Turing

era infinita para ambos costados. Por lo que la condicin de termino era encontrar las 3

cintas vacias al dirigirnos a la izquierda. Esto se puede implementar de igual forma si la

maquina rebota al llegar a un costado, simplemente revisar que el smbolo sea X, la nica


14/18


14

forma de que al ir a la izquierda de X y volver a encontrar X es que rebotemos por el

inicio del string (dado que X no estaba en el alfabeto de entrada)

Por ultimo la funcin del estado q11 es marcar con X el inicio de las 3 cintas y dejarnos

un carcter a la derecha de esto para comenzar a leer.

5.1.3 Bloque separar as, bs y cs

Ahora este bloque es el que separa los caracteres en diferentes cintas y rebobina otra vez las

cintas al inicio.

Ilustracin 6 Bloque separador rebobinador

El estado q12 va pasando las as sin modificarlas ya que estas deben quedar en la primera

cinta. Notar que ahora estamos haciendo que la segunda y tercera cinta no se muevan

ya que al colocar los caracteres iniciales X en el bloque anterior ahora si nos importa

colocar cada cinta en orden. Pueden ocurrir dos cosas para salir de este estado uno

encontarnos con una b en tal caso quitamos el smbolo de la primera cinta y avanzamos,

agregamos el smbolo a la segunda cinta y la avanzamos y no avanzamos la tercera cinta.


15/18


15

El otro caso es cuando llegamos al final de la entrada (nos encontramos un ) en tal caso

pasamos al estado q3 que rebobinara las as.

En el estado q0 se realiza un proceso anlogo al anterior solo que con los caracteres bs.

El estado q1 es lo mismo.

Algo importante es notar el trabajo del estado q16. Lo que ocurre es que al estar toda la

entrada en la primera cinta esta siempre debe ir avanzando para poder leer toda la

entrada. A consecuencia de esto al terminar de consumir la entrada las cintas quedan

asi.

o Xaaaa()

o Xbbb()

o Xcc()

Por esto mismo es necesario rebobinar los espacios vacos que dejo procesar la

entrada. Esto lo realiza el estado q16 retrocediendo solo la primera cinta en cada espacio

en blanco. Al terminar de rebobinar en la primera cinta nos encontramos o con el

carcter X (no se ingres ningn a) o con caracteres a que haban en la entrada. Esto seve reflejado en las transicin a estados q3 o q2

Los estados q3, q2, q15 realizan la misma funcin de q6 es decir rebobinar. Solo que

rebobinan de a una palabra a la vez.

Al terminar todos estos estados las cintas quedan de esta forma

o X(a)aaa

o X(b)bb

o X(c)c

5.1.4 Bloque de comparacin y aceptacin

Por ltimo el bloque final va borrando de a 3. Revisa que las cs se acaben al mismo tiempo que

las as o que las bs si se cumple esto debemos aceptar

Ilustracin 7 bloque de aceptacin


16/18


16

5.2Parte b

L4 = {x#y#z | x, y, z {0, 1} , |x| = |y|, z = xy}, donde es el XOR binario.

Para realizar este lenguaje realizare los siguientes pasos:

Parto con una mquina de Turing de 3 cintas

Primero marco los caracteres en las 3 cintas

Luego escribo en la primera cinta lo anterior al primer #. Escribo en la segunda cinta lo anterior

al segundo # y escribo lo posterior al segundo # en la tercera cinta.

Rebobino todas las cintas hasta llegar al primer carcter marcado

Ahora por comparo segn la tabla de verdad del XOR la primera segunda y tercera cinta. Esto lo

logro escribiendo estas reglas en 4 transiciones al mismo estado. Si no posee esta transicin se

sale y rechaza. Si al llegar al final encuentra las 3 cintas vacas es que proceso todocorrectamente. Esta forma tambin evita que las palabras sean de distinto largo ya que aunque

las transiciones sean vlidas llegara a un punto donde las 3 cintas no estarn vaca.

Aqu tambin asumo que siempre se colocan los 0 sin importar si son significativos por ejemplo. Si

1110 debe escribirse 01 no 1.

El diagrama es el siguiente

Ilustracin 8 P5 B diagrama de estados


17/18


17

5.2.1 Bloque de entrada marcar signo al inicio

El primer bloque no requiere mayor explicacin es el mismo bloque del problema anterior solo

que adaptado para trabajar con 1,0,#. Para mayor explicacin revisar bloque de entrada en parte a.

5.2.2 Bloque de separar y rebobinar

El segundo bloque permite colocar en cada cinta lo que corresponde el diagrama de estados es

el siguiente.

Ilustracin 9 Bloque de separacin y rebobinado. Permite que la comparacin sea fcil en la tercera a tercera etapa


18/18


18

El estado q7, q17, q19 tienen funciones similares a los estados que separaban en cintas en

el parte a). Sin embargo ahora toman todos los caracteres y los colocan en su cinta

correspondiente, si encuentran # avanzan al siguiente.

En el estado q3 retrocedemos la cinta 1. Esto se logra mediante sea cual sea el carcter que

leamos (menos el carcter X inicial) escribimos el mismo carcter y retrocedemos. No

movemos las dems cintas. Si ve el carcter X pasa al siguiente estado de rebobinar

De forma anloga se rebobinan cintas 2 y 3.

5.2.3 Bloque de aceptacin

Ilustracin 10 Bloque de aceptacin comprueba tabla de verdad de XOR

Ahora lo nico que resta es comprobar bit por bit si la tercera cinta contiene el resultado del XOR.

Esto se logra codificando la tabla de verdad del XOR en la transicin del estado q13. Si hace una

transicin valida se mantendr en el estado q13 y avanzara todas las cintas para probar el siguiente

bit. De no estar la transicin no es una operacin valida por lo que rechazamos. Por ultimo si se

vacian las 3 cintas a la vez quiere decir que todas las cintas tenan el mismo largo y que tambin

todas cumplieron la condicin del XOR. Por eso aceptamos

Documents

Tarea 2 Teoria de La Computacion Andres Ferrada Lagos