{"id":16165,"date":"2022-07-16T19:02:37","date_gmt":"2022-07-16T19:02:37","guid":{"rendered":"https:\/\/blogs.ugto.mx\/rea\/?p=16165"},"modified":"2022-09-24T02:57:06","modified_gmt":"2022-09-24T02:57:06","slug":"clase-digital-7-analisis-lexico-diseno-de-automatas-de-estado-finito","status":"publish","type":"post","link":"https:\/\/blogs.ugto.mx\/rea\/clase-digital-7-analisis-lexico-diseno-de-automatas-de-estado-finito\/","title":{"rendered":"Clase digital 7. An\u00e1lisis l\u00e9xico: Dise\u00f1o de aut\u00f3matas de estado finito"},"content":{"rendered":"\n\n\n<div class=\"wp-block-cover\" style=\"min-height:284px;aspect-ratio:unset;\"><span aria-hidden=\"true\" class=\"wp-block-cover__background has-background-dim-40 has-background-dim\"><\/span><img decoding=\"async\" class=\"wp-block-cover__image-background wp-image-18067\" alt=\"\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878.jpg\" style=\"object-position:39% 62%\" data-object-fit=\"cover\" data-object-position=\"39% 62%\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1280\" height=\"720\" class=\"wp-block-cover__image-background wp-image-18067\" alt=\"\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878.jpg\" style=\"object-position:39% 62%\" data-object-fit=\"cover\" data-object-position=\"39% 62%\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878.jpg 1280w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878-300x169.jpg 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878-1024x576.jpg 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/3415878-768x432.jpg 768w\" sizes=\"auto, (max-width: 1280px) 100vw, 1280px\" \/><\/noscript><div class=\"wp-block-cover__inner-container is-layout-flow wp-block-cover-is-layout-flow\">\n<p class=\"has-text-align-center has-base-3-color has-text-color has-large-font-size wp-block-paragraph\">An\u00e1lisis l\u00e9xico: Dise\u00f1o de aut\u00f3matas de estado finito<\/p>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"introduccion\">Introducci\u00f3n<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Hola!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Me da gusto encontrarte de nuevo en este ambiente de aprendizaje, espero que te encuentres con mucho \u00e1nimo por seguir adelante ya que faltan nuevos e interesantes temas que te servir\u00e1n en el futuro. Es por ello que te doy la bienvenida a la clase siete del curso.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En esta sesi\u00f3n aprenderemos sobre&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Empecemos y buena suerte!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"desarrollo-del-tema\">Desarrollo del tema <\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Construir Aut\u00f3mata a partir de ER:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Algoritmo de McNaughton-Yamada-Thompson<ul><li>Convierte una expresi\u00f3n regular en AFN<\/li><\/ul><\/li><li>RE \u2192 AFN (Construcci\u00f3n de Thompson) \u2192 AFD (Construcci\u00f3n de subconjunto) \u2192 Minimizaci\u00f3n de estados<ul><li>Descomposici\u00f3n en alfabetos b\u00e1sicos y operadores<\/li><li>Construir AF para alfabetos b\u00e1sicos<\/li><li>Combinaci\u00f3n de AFs por operador<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Construir Aut\u00f3mata a partir de ER:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>RE \u2192 AFD Transici\u00f3n_de_estado \u21d4 position_transition en patr\u00f3n \u2192 Minimizaci\u00f3n de estados<ul><li>Etiquetar s\u00edmbolos ER con etiquetas de posici\u00f3n<\/li><li>Obtener \u00e1rbol de sintaxis del patr\u00f3n etiquetado<\/li><li>calcular&nbsp;{<em>nullable<\/em>,&nbsp;<em>firstpos,<\/em>&nbsp;<em>lastpos<\/em>} de subexpresiones<\/li><\/ul><ul><li>calcular<em> follow(i)<\/em><\/li><li>s0&nbsp;=&nbsp;<em>firstpos(root)<\/em><\/li><\/ul><\/li><li>construir funci\u00f3n de transici\u00f3n de acuerdo a follow(i)<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Construir una AFN:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>\u00bfC\u00f3mo definir un AFN para una expresi\u00f3n regular?<ul><li>Simple. Una expresi\u00f3n regular se puede formar por&nbsp;<ul><li>Alternancia (|)&nbsp;<\/li><li>concatenaci\u00f3n y&nbsp;<\/li><li>Repetici\u00f3n (*, +)<\/li><\/ul><\/li><\/ul><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">S\u00f3lo requerimos saber c\u00f3mo construir el AFN para un solo s\u00edmbolo y c\u00f3mo componer AFNs<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">AFN para el s\u00edmbolo&nbsp;<em>a<\/em> (o ):<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Construir AFNs por Alternancia:<br>Dados dos AFNs N(s) y N(t), el AFN N(s|t) es:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Construir AFNs por Concatenaci\u00f3n:<br>Dados dos AFNs N(s) y N(t), el AFN N(st) es:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Construir AFNs por Repetici\u00f3n:<br>Dado el AFN N(s), el AFN N(s<sup>*<\/sup>) es:<br>Dado el AFN N(s), el AFN N(s?) es:<br>Dado el AFN N(s), el AFN N(s<sup>+<\/sup>) es:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Propiedades de los AFNs:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Tienen a lo m\u00e1s el doble de estados que el n\u00famero de s\u00edmbolos y operadores en&nbsp;<em>r<\/em><\/li><li>Tienen exactamente un estado inicial y un estado aceptador<\/li><li>Cada estado tiene a lo m\u00e1s una transici\u00f3n saliente en un s\u00edmbolo del alfabeto o a lo m\u00e1s dos transiciones salientes \u03b5<\/li><li>Todas las transiciones \u201cno determin\u00edsticas\u201d son introducidas por transiciones \u03b5 que se conectan a\/desde estados iniciales\/finales.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Convertir AFN a AFD:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Cada estado del AFD (D) corresponde a un conjunto de estados de AFN (N)<ul><li>Transformar N en D por medio de construcci\u00f3n de subconjunto<\/li><\/ul><\/li><li>D estar\u00e1 en el estado {x, y, z} despu\u00e9s de leer una cadena dada si y s\u00f3lo si N podr\u00eda estar en cualquiera de los estados x, y o z dependiendo de las transiciones que haga<br><br>D lleva cuenta de todas las posibles rutas que N podr\u00eda tomar y las ejecuta en paralelo<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Minimizaci\u00f3n de N\u00famero de Estados:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Cada AFD tiene un \u00fanico AFD equivalente m\u00e1s peque\u00f1o.<\/li><li>Dado un AFD M, usar divisi\u00f3n para construir el AFD equivalente m\u00ednimo.&nbsp;<\/li><li>En realidad unimos estados individuales al conjunto m\u00e1s grande de estados, en vez de dividir a lo loco.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"conclusion\">Conclusi\u00f3n<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Para recordar:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Felicidades, est\u00e1s avanzando muy bien! Espero que el tema te haya gustado y despierte tu inter\u00e9s para seguir investigando sobre ello. Recuerda elaborar y mandar la consigna de esta clase, te espero en la pr\u00f3xima sesi\u00f3n donde aprender\u00e1s un tema relevante para tu formaci\u00f3n acad\u00e9mica. Hasta pronto.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"fuentes-de-informacion\">Fuentes de informaci\u00f3n<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/www.youtube.com\/watch?v=uUuf9fJ4tgY\" target=\"_blank\" rel=\"noreferrer noopener\">Expresi\u00f3n Regular a AFN &#8211; Algoritmo de Thompson, 0:06 \u2013 3:13.<\/a><\/li><li><a href=\"https:\/\/ivanzuzak.info\/noam\/webapps\/fsm_simulator\/\" target=\"_blank\" rel=\"noreferrer noopener\">FSM Simulator &#8211; Ivan Zuzak&#8217;s homepage<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Introducci\u00f3n \u00a1Hola! Me da gusto encontrarte de nuevo en este ambiente de aprendizaje, espero que te encuentres con mucho \u00e1nimo por seguir adelante ya que faltan nuevos e interesantes temas que te servir\u00e1n en el futuro. Es por ello que te doy la bienvenida a la clase siete del curso. En esta sesi\u00f3n aprenderemos sobre&nbsp; &#8230; <a title=\"Clase digital 7. An\u00e1lisis l\u00e9xico: Dise\u00f1o de aut\u00f3matas de estado finito\" class=\"read-more\" href=\"https:\/\/blogs.ugto.mx\/rea\/clase-digital-7-analisis-lexico-diseno-de-automatas-de-estado-finito\/\" aria-label=\"Leer m\u00e1s sobre Clase digital 7. An\u00e1lisis l\u00e9xico: Dise\u00f1o de aut\u00f3matas de estado finito\">Leer m\u00e1s<\/a><\/p>\n","protected":false},"author":142,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_crdt_document":"","episode_type":"","audio_file":"","podmotor_file_id":"","podmotor_episode_id":"","cover_image":"","cover_image_id":"","duration":"","filesize":"","filesize_raw":"","date_recorded":"","explicit":"","block":"","itunes_episode_number":"","itunes_title":"","itunes_season_number":"","itunes_episode_type":"","footnotes":""},"categories":[180,19,471],"tags":[41,472,473],"class_list":["post-16165","post","type-post","status-publish","format-standard","hentry","category-cideap","category-ingenieria-en-sistemas-computacionales","category-uda-compiladores","tag-clase-digital","tag-iili06025","tag-jose-ruiz-pinales"],"acf":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/users\/142"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/comments?post=16165"}],"version-history":[{"count":4,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16165\/revisions"}],"predecessor-version":[{"id":19161,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16165\/revisions\/19161"}],"wp:attachment":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/media?parent=16165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/categories?post=16165"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/tags?post=16165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}