Cantu Teoria de Automatas 1e Recortables

7/23/2019 Cantu Teoria de Automatas 1e Recortables

1/112

Teora de autmatas.Un enfoqueprctico

Recortables

Thelma Cant Mara Gpe. Mendoa


2/112

!echa" # #

1.1 Bsqueda de

$lumno"

Teora de autmatas. Un enfoqueprctico %

&ombre del

len'ua(e

)*nde se utilia+ )Cul es el beneficiopara la humanidad+

,

$lfabeto"

&ombre del

len'ua(e )*nde se utilia+ )Cul es el beneficiopara la humanidad+

%

$lfabeto"

&ombre del


-

$lfabeto"

&ombre del


$lfabeto"

&ombre del


/

$lfabeto"


3/112

!echa" # #

1.2 Ejercicios de conjuntos

$lumno"

Con(untos" $ = 0ab1bc1 cd23 = 0aa1b1 cc2

C = 0a1 b1 c2* = 0b1 d1 e24 = 0b1 d1 f2! = 0a1 f1 '1 h1 i1 (2

G = 04d'ar1 Carlos1 4u'enio1 $lan1 Marco1 5ess1 Re61 7ibrado1 $'ustn2

8 = 08errera1 4d'ar1 5ure1 Martne1 &ampul1 9ols1 :ida;a1 Gonle2


4/112

!echa" # #

1.3 Cuadro co!arati"o de las caracter#sticas de 10 lenguajesde !rograaci$n de alto ni"el

7en'ua(e $plicacin

Tipo depro'ramacin

7en'ua(epro'ramado


5/112

1.4 %#nea de tie!o

$lumno"

4labore una lnea de tiempo >por dcadas 6 'eneraciones? que inclu6a las caractersticas de

los len'ua(es conbase en el desarrollo del hardDare.


6/112

!echa" # #

1.5 Cuadro sin$!tico

$lumno"

4labore un cuadro sinptico o esquemapara or'aniar los conceptos relatiBos a los

diferen@ tes tipos de len'ua(es depro'ramacin. Trate de ir de lo 'eneral a lo particular.


7/112

!echa" # #

1.6 &'cnicas de

$lumno"

EnBesti'ue >por lo menos? cinco diferentes tcnicas debsqueda. Enclu6a sus aplicaciones 6

caractersticasprincipales.

Tcnica de bsqueda $plicacin Caractersticas

,

%

-

/


8/112

!echa" # #

2.1 )e*inici$n regular

$lumno"

*ise;e la definicin re'ularpara un len'ua(e depro'ramacin en len'ua(e natural >espa@

;ol?.

Nota" *efina cada una de las eFpresiones re'ulares que inte'ran la definicin re'ular.


9/112

!echa" # #

2.2 )e*inici$n regular de +,%

$lumno"

*ise;e una definicin re'ular para analiar una entrada UR7 >Uniform Resource Locator?1

es decir1 la direccin de un sitio de Enternet.

Nota" *efina cada una de las eFpresiones re'ulares que inte'ran la definicin re'ular.


10/112

Teora de autmatas. Un enfoqueprctico

!echa" # #

2.3 )e*inici$n regular del ,-C

$lumno"

*ise;e una definicin re'ularpara analiar el Re'istro !ederal de Contribu6entes.

Nota" *efina cada eFpresin re'ular que inte'ra a la definicin re'ular.


11/112

!echa" # #

2.4 )e*inici$n regular de C+,

$lumno"

*ise;e una definicin re'ularpara la claBe CUR=.

Nota" *efinir cada una de las eFpresiones re'ulares que inte'ran la definicin re'ular.


12/112

!echa" # #

3.1 /l*a(eto

$lumno"

*efina el alfabetopara cada dia'rama de transicin de los operadores de eFpresiones

re'ula@ res que se presentan1 6 describa breBemente el si'nificado de la representacin'rfica.

*escripcin

$lternatiBo *T,

$lternatiBo *T%

Unario


13/112

!echa" # #

3.2 0atri1 de

$lumno"

*ise;e la matri de transicinpara cada uno de los dia'ramas del desprendible -.,.

$lternatiBo *T,"

$lfabeto

4stado 7 * del C$T

,

%

-

Unario


14/112

!echa" # #

3.3 Eleentos de de*inici$n *oral de un

$lumno"

=ara cada autmata finito definido en la seccin de dia'ramas de transicin1 obten'a

los elementos correspondientes de la definicin formal del autmata1 e identifique el tipode autmata.

J q !Tipo de

autmata

$lternatiBo *T,

$lternatiBo *T%

Unario


15/112

!echa" # #

3.4 )oinio de la de*inici$n *oral de aut$atas /-) en

$lumno"

Complete los elementos de la definicin formal de autmatas 6 los dia'ramas de

transicin correspondientes1 tome comobase las si'uientes tablas de transicin deestados.

1. q = q

! = 0q%1 q2

2. q = q! = 0q1 q-2

,

q 0q1 q,2 0q1 q-2

q, 02 0q%2

q% 0q%2 0q%2

q- 0q2 02

q 0q2 0q2

a b

q 0q2 0q-1 q%2

q, 0q1 q%2

q% 0q1 q,1 q%2 0q1 q,2

q- 0q2 0q-2


16/112

!echa" # #

3.5 Con"ersi$n de /-) a

$lumno"

ConBierta cada $!&* del desprendible -. a $!*K desarrolle elprocesopor pasos.


17/112

!echa" # #

3.6 )iagraa de transici$n de estados iniiados

$lumno"


18/112

!echa" # #

4.1 0a!a cogniti"o

$lumno"

4labore un mapa co'nitiBo de las caractersticas 6 operacin de las mquinas de Turin'.


19/112

!echa" # #

4.2 Cuadro co!arati"o

$lumno"

4labore un cuadro comparatiBo que ilustre las diferencias 6 seme(anas entre los

autmatas finitos 6 las mquinas de Turin'.

Condicin $! MT

Cantidad de estados iniciales

Cantidad de estados finales

=roblemas al aceptar la cadena

7ectura de la cadena

4stado de error

$ceptacin de la cadena

Tratamiento de la cadena de entrada

MoBimientos adicionales

!uncionalidad


20/112

!echa" # #

4.3 )iagraa de 3quinas de

$lumno"

Tomando en cuenta las propuestas si'uientes1 realice los dia'ramas de mquinas de

Turin' necesarios e identifique los elementos que componen la definicin formal.1. 4ncontrar el si'uientepatrn en la cadena a partir de laprimera celda" FF6. )4n

qu situacin esta mquina de Turin' podra tener un problema de parada+

2. 4liminar todos los smbolos del alfabeto a partir de la celda actual 6 hasta

encontrar unblancoK la posicin final del cabeal debe ser la celda en donde inici

sus clculos.


21/112

!echa" # #

4.4 03quinas de &uring

$lumno"

*ise;e mquinas de Turin' compuestaspara cada mquina del desprendible .-.

1. 4ncontrar el si'uientepatrn en la cadena a partir de la primera celda" FF6.

2. 4liminar todos los smbolos del alfabeto a partir de la celda actual 6 hasta

encontrar unblancoK la posicin final del cabeal debe ser la celda en donde inici

sus clculos.


22/112


!echa" # #

4.5 03quina de &uring secuencia de con*iguraciones

$lumno"

*ise;e una mquina de Turin' para cada uno de los si'uientes len'ua(esK determine los

elementos de la definicin formal 6 la secuencia de las confi'uraciones de la cadenapara cada mquina.

1. 7 = 0>F6?m>F6?nK m1 n&+2Kconfi'uracin inicial de la cinta"

F6F6F6F6F6...2. 7 = 0 >abc,?mK m&+2Kconfi'uracin inicial de la cinta" abc,abc,abc,L3. 7 = 0albmcnd;K l1 m1 n1 ;>=%2K confi'uracin inicial de la cinta"

aaaabbbccddL4. 7 = 0,?n>,?mK n1 m&+2Kconfi'uracin inicial de la cinta"

,,@,,L


23/112

!echa" # #

4.6 .rograaci$n de una 3quina de

$lumno"

*ise;e1 a partir de las caractersticas si'uientes1 unpro'rama que simule el

comportamiento de las mquinas de Turin'1 inclu6endo la confi'uracin de cinta"1. 4lpro'rama proporciona un men de operaciones bsicas de las mquinas de Tu@

rin'1 a traBs del cual el usuario puede hacer elecciones para formar una

mquina compuesta.

2. 4l usuario proporciona la cadena de entrada.

3. 4l usuario proporciona la posicin de la celda en donde inicia los clculos la

mqui@ na de Turin'.

Consideraciones !ara la e"aluaci$n del !ro*esor

Cantidad de elementos en el men de operaciones

=resentacin del alfabeto

=resentacin de la cadena mediante celdas)4Fiste la opcin para colocar el cabeal en la

cinta+ :isualiacin 'rfica de la mquina

=rocesoporpasos de los moBimientos de la mquina

MoBimientos del cabeal a medida que aBana la mquina de Turin'

)8a6 problema deparada+

$ceptacin de la cadena


24/112

!echa" # #

5.1 )iseo de un lenguaje de !rograaci$n !ro!io

$lumno"

Enstruccin *escripcin 9intaFis $r'umentos


25/112

!echa" # #


Teora de autmatas. Un enfoqueprctico 25


26/112

!echa" # #




27/112

!echa" # #




28/112

!echa" # #




29/112

!echa" # #




30/112

!echa" # #




31/112

!echa" # #




32/112

!echa" # #


33/112

!echa" # #


34/112

!echa" # #


35/112

!echa" # #

5.2 )e*inici$n regular de un lenguaje !ro!io

$lumno"

&ombre 4Fpresin re'ular



36/112

!echa" # #

&ombre 4Fpresin re'ular



37/112


Consideraciones !ara la e"aluaci$n del !ro*esorContenido de las definiciones re'ulares"

9mbolo inicial

4Bita la ambi'Nedad

=alabras reserBadas


38/112


!echa" # #

5.3 )iagraa tu !ro!io lenguaje

$lumno"

)iagraa de transici$n


39/112


!echa" # #

)iagraa de transici$n


40/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido del dia'rama de transicin"

4stado inicial

4stados finales definidos

4Bita la ambi'Nedad

=alabras reserBadas


41/112


!echa" # #

5.4 0atri1 de un lenguaje de !rograaci$n !ro!io

$lumno"

Nota: Realiar esta matri en un archiBo de 4Fcel con las columnas 6 filas necesarias.


42/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido de la matri de transicin"

Caracteres aceptados por el len'ua(e

4stadosbien definidos

Columna de toQens

ToQens definidos en los estados finales

*efinicin de las casillas Bacas

=alabrasreserBadas


43/112


!echa" # #

5.5 .rograaci$n de un anali1ador l'ico !ro!io

$lumno"

&ombredelpro'ramae(ecutable"

Ente'rantesdelequipo"

*escribalaspartesenquesediBidielproductofinal"

4specifique de qu manera fueron asi'nadas dichas partes entre los inte'rantes del equipo"

Tiempo estimado de pro'ramacin"

Tiemporealdepro'ramacin"

9iha6diferenciaentreambostiemposeFpliqueporqu"

&mero de lneas depro'ramacin que se compilaron"

Tiempode e(ecucin"

&ombredel archiBo de toQens resultante"

Tipode estructura de datos utiliada como tabla de smbolos"

4Fpliqueporqueli'ieronesetipo deestructuradedatos"


44/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido de la Bista del pro'rama"

7nea a compilar

ConBersin simultnea a toQens

7nea resultante en toQens

&mero de lnea

*esplie'ue de error >si es que aplica?

&mero de errores

Genera reporte de errores inclu6endo las lneas

Car'a como archiBo elpro'rama a compilar

4Baluacin"


45/112


!echa" # #

6.1 )iagraa de sintais

$lumno"

)iagraa de sinta7is


46/112


!echa" # #

)iagraa de sinta7is


47/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido del dia'rama de sintaFis"

Manipulacin adecuada de los smbolos

$r'umentos bien definidos &merode instrucciones correctas &mero de

instrucciones incompletas

4Baluacin"


48/112


!echa" # #

6.2 8r(ol de deri"aci$n

$lumno"

8r(ol de deri"aci$n


49/112


!echa" # #

8r(ol de deri"aci$n


50/112


!echa" # #


Contenido del rbol de deriBacin"


$r'umentos bien definidos &merode instrucciones correctas &mero de


4Baluacin"


51/112

!echa" # #

6.3 9ra3tica li(re de conteto

$lumno"

Equierdo *erecho


52/112

!echa" # #

Equierdo *erecho



53/112



Contenido de la 'ramtica libre de conteFto"


$r'umentos bien definidos &mero

de instrucciones correctas &mero de


4Baluacin"


54/112


!echa" # #

6.4 )iagraas de *lujo

$lumno"

)iagraas de *lujo


55/112


!echa" # #

)iagraas de *lujo


56/112


!echa" # #


Contenido del dia'rama de flu(o"


$naliador recursiBo descendente

9oluciona diBersos e(emplos

$naliador recursiBo ascendente

9oluciona diBersos e(emplos

4Baluacin"


57/112


!echa" # #

6.5 .rograaci$n de un anali1ador sint3ctico !ro!io

$lumno"







9iha6diferenciasentreambostiempos1eFpliqueporqu"


Tiempode e(ecucin"


4Fpliquelaranporlaqueeli'ieronesetipo deestructuradedatos"


58/112


!echa" # #


Contenido de la Bista del pro'rama"

7nea a compilar

ConBersin simultnea de la cadena de entrada7nea resultante

&mero de lnea


&mero de errores

Genera reporte de errores1 inclu6endo las lneas

Car'a como archiBo el archiBo de toQens

4Baluacin"


59/112


!echa" # #

7.1 8r(oles de e!resi$n

$lumno"

8r(oles de e7!resi$n


60/112


!echa" # #

8r(oles de e7!resi$n


61/112

!echa" # #


Contenido del rbol de eFpresin"

ConBersin adecuada del rbol de deriBacin

$r'umentos bien definidos &mero

de instrucciones correctas &mero de


4Baluacin"


62/112

7.2 ,eglas senticas

$lumno"

Equierdo *erecho


63/112

!echa" # #

Equierdo *erecho



64/112


65/112


!echa" # #

7.3 .rograa tu anali1ador sentico

$lumno"




4specifique de qu manera fue asi'nada cada una de las partes entre los inte'rantes del

equipo"



9iha6diferenciaentreambostiempos1eFpliqueporqu"

Tipo de analiador que se eli'i pro'ramar" , pasada 1 % pasadas 1 - pasadas


Tiempode e(ecucin"




66/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido de la Bista del pro'rama"

7nea a compilar

ConBersin simultnea de la cadena de entrada

7nea resultante

&mero de lnea


&mero de errores

Genera reporte de errores1 inclu6endo las lneas

Car'a como archiBo el archiBo de toQens

&mero de pasadas

$ctualiacin de la tabla de smbolos

ConBersin del archiBo temporal

!uncionamiento del mtodo recursiBo

Contadores de instrucciones compuestas

Tiempo de e(ecucin de cada pasada

4Baluacin"


67/112


!echa" # #

8.1 )iagraa de *lujo de con"ersi$n a notaci$n !re*ijo

$lumno"

)iagraa de *lujo !re*ijo


68/112


!echa" # #

)iagraa de *lujo !re*ijo


69/112


!echa" # #

Consideraciones !ara la e"aluaci$n del !ro*esorContenido del dia'rama de flu(o"


ConBersin eFitosa

Contempla el uso de los parntesis

Contempla operaciones mltiples

4Baluacin"


70/112


!echa" # #

8.2 )iagraa de *lujo de con"ersi$n a notaci$n !ost*ija

$lumno"

)iagraa de *lujo !ost*ijo


71/112


!echa" # #

)iagraa de *lujo !ost*ijo


72/112


73/112


!echa" # #

8.3 .rograaci$n de un con"ertidor a notaci$n !re*ija o !ost*ija

$lumno"







9iha6diferenciasentreambostiempos1eFpliqueporqu"

)Ju diferencia obserBa en cuanto a comple(idad entre lapro'ramacin de ambas nota@

ciones+

&mero de conBersiones con que se hicieron pruebas"

Tiempode e(ecucin"

Tipode estructura de datos utiliada"



74/112

!echa" # #



Captura de la eFpresin aritmtica

9eleccin entre las dos notaciones

7nea resultante

Mane(o de losparntesis


Tiempo de e(ecucin

4Baluacin"


75/112

8.4 Construcci$n de una tri!leta

$lumno"

,

%

-

/

O

P

,

,,

,%

,-

,

,/

,

,

,O

,P

%

%,

%%

%-

%

%/

%

%

%O

%P

-

-,

-%

--

-

-/

Triplo

*ato ob(eto *ato fuente


76/112

Consideraciones !ara la e"aluaci$n del !ro*esorContenido de las tripletas"


77/112

8.5 Construcci$n de un cudru!lo

$lumno"

,

%

-

/

O

P

,

,,

,%

,-

,

,/

,

,

,O

,P

%

%,

%%

%-

%

%/

%

%

%O

%P

-

-,

-%

--

-

-/

Cudruplo

*ato ob(eto *ato fuente , *ato fuente %


78/112

Consideraciones !ara la e"aluaci$n del !ro*esorContenido de los cudruplos"


79/112


80/112


!echa" # #



7ectura del pro'rama fuente

9eleccin entre las dos tcnicas

4structuras resultantes

&mero de instrucciones correctas

&mero de instrucciones incorrectas

Tiempo de e(ecucin

4Baluacin"


81/112


!echa" # #

9.1 )etecci$n de e7!resiones locales susce!ti(les de o!tiiaci$n

$lumno"

$l'oritmo


82/112

!echa" # #

$l'oritmo



83/112


84/112


85/112


86/112


87/112


88/112

!echa" # #



7ectura de tripletas o cudruplos

Modificacin adecuada del cdi'o intermedio:isualiacinpreBia 6posterior



Tiempo de e(ecucin

4Baluacin"


89/112

9.4 )etecci$n de (ucles

$lumno"

$l'oritmo


90/112

!echa" # #

$l'oritmo



91/112


92/112


!echa" # #

9.5 )iagraa de *lujo de detecci$n de (ucles

$lumno"

)iagraa de *lujo de detecci$n de (ucles


93/112


!echa" # #

)iagraa de *lujo de detecci$n de (ucles


94/112


!echa" # #




*eteccin eFitosaCorreccin eFitosa

4Baluacin"


95/112


!echa" # #

9.6 .rograa tu detector de (ucles

$lumno"








)Ju diferencia obserBa en cuanto a comple(idad entre lapro'ramacin de ambas tcnicas+


Tiempode e(ecucin"




96/112


97/112

!echa" # #

9.7 )etecta los %:B/%E;

$lumno"

$l'oritmo


98/112


99/112

Teora de autmatas. Un enfoqueprctico PP


Contenido del al'oritmo"

Toma como entrada los triplos o cudruplos

*etecta losproblemas 'lobales


100/112


!echa" # #

9.8 )iagraa de *lujo de detecci$n de !ro(leas glo(ales

$lumno"

E7!resiones glo(ales


101/112


102/112


!echa" # #




*eteccin eFitosa

Correccin eFitosa

4Baluacin"


103/112


!echa" # #

9.9 .rograaci$n de un detector de !ro(leas glo(ales

$lumno"





equipo"






Tiempode e(ecucin"Tipode estructura de datos utiliada"



104/112


105/112

9.10 )etecta los irillas

$lumno"

$l'oritmo


106/112

!echa" # #

$l'oritmo



107/112


108/112


!echa" # #

9.11 )iagraa de *lujo de detecci$n de irillas

$lumno"

E7!resiones irillas


109/112


110/112


!echa" # #




*eteccin eFitosa

Correccin eFitosa

4Baluacin"


111/112

Teora de autmatas. Un enfoqueprctico ,,,

!echa" # #

9.12 .rograa tu detector de irillas

$lumno"





equipo"






Tiempode e(ecucin"




112/112

!echa" # #



7ectura de tripletas o cudruplos

Modificacin adecuada del cdi'o intermedio:isualiacinpreBia 6posterior



Tiempo de e(ecucin

4Baluacin"

Documents

Cantu Teoria de Automatas 1e Recortables