{"id":16163,"date":"2022-07-16T19:01:53","date_gmt":"2022-07-16T19:01:53","guid":{"rendered":"https:\/\/blogs.ugto.mx\/rea\/?p=16163"},"modified":"2022-09-24T02:56:16","modified_gmt":"2022-09-24T02:56:16","slug":"clase-digital-6-analisis-lexico-automatas-de-estado-finito","status":"publish","type":"post","link":"https:\/\/blogs.ugto.mx\/rea\/clase-digital-6-analisis-lexico-automatas-de-estado-finito\/","title":{"rendered":"Clase digital 6. An\u00e1lisis l\u00e9xico: 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-18060\" alt=\"turned-on monitor\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea.jpg\" style=\"object-position:64% 83%\" data-object-fit=\"cover\" data-object-position=\"64% 83%\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1600\" height=\"1067\" class=\"wp-block-cover__image-background wp-image-18060\" alt=\"turned-on monitor\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea.jpg\" style=\"object-position:64% 83%\" data-object-fit=\"cover\" data-object-position=\"64% 83%\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea.jpg 1600w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea-300x200.jpg 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea-1024x683.jpg 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea-768x512.jpg 768w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea-1536x1024.jpg 1536w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/zgzskfnsbea-272x182.jpg 272w\" sizes=\"auto, (max-width: 1600px) 100vw, 1600px\" \/><\/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: 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\">Qu\u00e9 gusto poder encontrarte en esta nueva sesi\u00f3n, espero que sigas descubriendo este curso y lo sigas viendo fascinante. Por lo tanto, te doy la m\u00e1s cordial bienvenida a esta clase digital 6.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En esta sesi\u00f3n aprenderemos sobre la teor\u00eda y antecedentes de los aut\u00f3matas finitos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Los aut\u00f3matas finitos son capaces de reconocer lenguajes regulares. De hecho, las expresiones regulares se pueden implementar usando aut\u00f3matas finitos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En teor\u00eda, para cada expresi\u00f3n regular, existe un aut\u00f3mata finito no determin\u00edstico y un aut\u00f3mata finito determin\u00edstico que la pueden reconocer.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La teor\u00eda de aut\u00f3matas (o teor\u00eda de la computaci\u00f3n) es una rama te\u00f3rica de las ciencias computacionales que estudia m\u00e1quinas abstractas y aut\u00f3matas, as\u00ed como los problemas computacionales que se pueden resolver con ellos. Por lo tanto, la teor\u00eda de los aut\u00f3matas finitos es muy importante para los ingenieros de ciencias computacionales.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El conocimiento sobre la teor\u00eda de los aut\u00f3matas finitos y su relaci\u00f3n con las expresiones regulares permite comprender mejor el dise\u00f1o e implementaci\u00f3n de analizadores l\u00e9xicos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En conclusi\u00f3n, la teor\u00eda de los aut\u00f3matas de estado finito tiene relaci\u00f3n con la teor\u00eda de los lenguajes formales que vimos en la sesi\u00f3n anterior.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Otra raz\u00f3n para conocer sobre la teor\u00eda de los aut\u00f3matas de estado finito es que las herramientas Lex y flex generan aut\u00f3matas finitos no determin\u00edsticos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Existen dos tipos de aut\u00f3matas finitos: Aut\u00f3matas finitos determin\u00edsticos y Aut\u00f3matas finitos no determin\u00edsticos. Ambos tipos de aut\u00f3matas son capaces de reconocer los mismos lenguajes regulares.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Sin m\u00e1s pre\u00e1mbulo, \u00a1comencemos!&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1\u00c9xito!<\/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\">Teor\u00eda de aut\u00f3matas:<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">La teor\u00eda de aut\u00f3matas (o teor\u00eda de la computaci\u00f3n) es una rama te\u00f3rica de las ciencias computacionales que estudia m\u00e1quinas abstractas y aut\u00f3matas, as\u00ed como los problemas computacionales que se pueden resolver con ellos. La palabra aut\u00f3mata proviene de la palabra griega \u03b1\u1f50\u03c4\u03cc\u03bc\u03b1\u03c4\u03bf\u03c2, que significa \u00abauto actuaci\u00f3n, voluntad propia, auto movimiento\u00bb. Un aut\u00f3mata (Aut\u00f3matas en plural) es un dispositivo inform\u00e1tico autopropulsado abstracto que sigue autom\u00e1ticamente una secuencia predeterminada de operaciones.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Los aut\u00f3matas finitos s\u00f3lo son capaces de reconocer lenguajes regulares. De hecho, las expresiones regulares fueron implementadas por primera vez por Thompson usando aut\u00f3matas finitos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El an\u00e1lisis l\u00e9xico est\u00e1 basado en expresiones regulares para el reconocimiento de las unidades del lenguaje o tokens.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Reconocimiento de Tokens:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>El objetivo del reconocimiento de tokens es construir un analizador l\u00e9xico que produzca tokens y los valores de sus atributos asociados<br>Existen dos m\u00e9todos para implementar el reconocimiento de tokens: manual o basado en herramientas.&nbsp;<\/li><\/ul>\n\n\n\n<ol class=\"wp-block-list\"><li>El m\u00e9todo manual consiste en construir o dise\u00f1ar y simular aut\u00f3matas finitos (AF\/AEF: Aut\u00f3mata (de Estado) Finito).<\/li><li>El m\u00e9todo basado en herramientas consiste en usar expresiones regulares para que el generador de c\u00f3digo construya los aut\u00f3matas finitos para el analizador l\u00e9xico.<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Aut\u00f3mata (de Estado) Finito:<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Un aut\u00f3mata finito se puede especificar por medio de:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Un conjunto de estados:&nbsp;<\/li><li>S<\/li><li>Un conjunto de s\u00edmbolos de entrada:<\/li><li>Una funci\u00f3n de transici\u00f3n: s,a=s&#8217;<\/li><li>Un estado inicial: s0<\/li><li>Un conjunto de estados finales: F<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Un aut\u00f3mata finito se puede representar de forma gr\u00e1fica por medio de un diagrama de transici\u00f3n de estados.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Existen dos tipos de aut\u00f3matas finitos:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Aut\u00f3matas finitos determin\u00edsticos (AFD)<br>Los cuales se caracterizan por tener a lo m\u00e1s una transici\u00f3n para cada s\u00edmbolo de entrada.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Aut\u00f3matas finitos no determin\u00edsticos (AFN)<br>Los cuales pueden tener m\u00e1s de una transici\u00f3n para alg\u00fan s\u00edmbolo de entrada.<\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Aut\u00f3mata Finito Determin\u00edstico:<\/h4>\n\n\n\n<ul class=\"wp-block-list\"><li>Un AFD es un caso especial de AFN en el cual:<br>Ning\u00fan estado tiene transici\u00f3n \u03b5<br>Para cada estado&nbsp;<em>s<\/em> y s\u00edmbolo de entrada <em>a <\/em>hay a lo m\u00e1s una etiqueta a que sale del estado <em>s<\/em><\/li><\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Aut\u00f3mata Finito No Determin\u00edstico:<\/h4>\n\n\n\n<ul class=\"wp-block-list\"><li>Un AFN se puede representar por medio de:<\/li><\/ul>\n\n\n\n<ol class=\"wp-block-list\"><li>S: un conjunto finito de estados<\/li><li>: un conjunto finito de s\u00edmbolos de entrada<\/li><li>: una funci\u00f3n de transici\u00f3n que mapea pares (estado, s\u00edmbolo) a estados<\/li><li>s0: un estado llamado estado inicial<\/li><li>F: un conjunto de estados llamado estados finales<\/li><\/ol>\n\n\n\n<ul class=\"wp-block-list\"><li>Un AFN acepta una cadena de entrada s si y s\u00f3lo si hay alguna ruta en el diagrama de transici\u00f3n desde el estado inicial hasta alg\u00fan estado final tal que las etiquetas a lo largo de la ruta se escriban como s<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Un aut\u00f3mata finito no determin\u00edstico puede simularse por medio de:<br><ul><li>Retroceso\/Respaldo: (Recorrido Secuencial)<br>Recordar siguiente configuraci\u00f3n alternativa (entrada actual y siguiente estado alternativo) cuando opciones alternativas son posibles<br><\/li><\/ul><ul><li>Paralelismo: (Recorrido en Paralelo)<br>Rastrear todas las alternativas posibles en paralelo<br><\/li><\/ul><ul><li>B\u00fasqueda hacia adelante:<br>Buscar m\u00e1s s\u00edmbolos de entrada para hacerla determin\u00edstica.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Para la simulaci\u00f3n de una AFN son necesarias las siguientes operaciones:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u03b5-<em>closure<\/em>:&nbsp;<br>Conjunto de estados alcanzables sin consumir ning\u00fan s\u00edmbolo de entrada.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>\u03b5-<em>closure<\/em>(<em>s<\/em>):&nbsp;<br>Conjunto de estados alcanzables desde el estado&nbsp;<em>s<\/em> por las transiciones-<em>\u03b5<\/em> solamente.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>\u03b5-<em>closure<\/em>(<em>S<\/em>):&nbsp;<br>Conjunto de estados alcanzables desde alg\u00fan estado s en S por las transiciones-<em>\u03b5<\/em> solamente.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li><em>move<\/em>(<em>S<\/em>, <em>c<\/em>):&nbsp;<br>Conjunto de estados hacia los que hay una transici\u00f3n con el s\u00edmbolo de entrada c desde alg\u00fan estado s en S.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Reconocimiento de una ER:<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Un AFN es m\u00e1s dif\u00edcil de simular<\/li><li>Un AFN es m\u00e1s f\u00e1cil de construir<\/li><\/ul>\n\n\n\n<ol class=\"wp-block-list\"><li>Construir un AFN<br><\/li><li>Construir un AFD equivalente<br>Predefinir los estados alcanzables y precalcular todas las posibles transiciones en vez de simular las transiciones paralelas en tiempo de ejecuci\u00f3n<\/li><\/ol>\n\n\n\n<ol class=\"wp-block-list\" start=\"3\"><li>(opcional) Minimizaci\u00f3n de Estados<br><\/li><li>Simular el AFD<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Lex y flex utilizan aut\u00f3matas finitos no determin\u00edsticos<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"conclusion\">Conclusi\u00f3n<\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Los aut\u00f3matas finitos s\u00f3lo son capaces de reconocer lenguajes regulares.<br><\/li><li>El an\u00e1lisis l\u00e9xico est\u00e1 basado en expresiones regulares para el reconocimiento de las unidades del lenguaje o tokens.<br><\/li><li>El objetivo del reconocimiento de tokens es construir un analizador l\u00e9xico que produzca tokens y los valores de sus atributos asociados.<br><\/li><li>Existen dos m\u00e9todos para implementar el reconocimiento de tokens: manual o basado en herramientas.<br><br>a) El m\u00e9todo manual consiste en construir o dise\u00f1ar y simular aut\u00f3matas finitos (AF\/AEF: Aut\u00f3mata (de Estado) Finito).<br><br>b) El m\u00e9todo basado en herramientas consiste en usar expresiones regulares para que el generador de c\u00f3digo construya los aut\u00f3matas finitos para el analizador l\u00e9xico.<\/li><\/ol>\n\n\n\n<ol class=\"wp-block-list\" start=\"5\"><li>Existen dos tipos de aut\u00f3matas finitos:<br><br>a)Aut\u00f3matas finitos determin\u00edsticos (AFD).<br>Los cuales se caracterizan por tener a lo m\u00e1s una transici\u00f3n para cada s\u00edmbolo de entrada.<br><br>b)Aut\u00f3matas finitos no determin\u00edsticos (AFN).<br>Los cuales pueden tener m\u00e1s de una transici\u00f3n para alg\u00fan s\u00edmbolo de entrada.<\/li><\/ol>\n\n\n\n<ol class=\"wp-block-list\" start=\"6\"><li>La simulaci\u00f3n de aut\u00f3matas finitos no determin\u00edsticos es m\u00e1s dif\u00edcil y requiere calcular:<br><br>a) \u03b5-<em>closure<\/em>(<em>S<\/em>). Es el conjunto de estados alcanzables desde alg\u00fan estado s en S por las transiciones-\u03b5 solamente.<br><br>b) <em>move<\/em>(<em>S<\/em>, <em>c<\/em>). Es el conjunto de estados hacia los que hay una transici\u00f3n con el s\u00edmbolo de entrada c desde alg\u00fan estado s en S.<\/li><\/ol>\n\n\n\n<ol class=\"wp-block-list\" start=\"7\"><li>Por otro lado, un aut\u00f3mata finito no determin\u00edstico es m\u00e1s f\u00e1cil de dise\u00f1ar.<br><\/li><li>Sin embargo, un aut\u00f3mata finito no determin\u00edstico se puede convertir en un aut\u00f3mata finito determin\u00edstico el cual es m\u00e1s f\u00e1cil de simular.<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Te felicito por llegar hasta aqu\u00ed con ese \u00edmpetu tan incontrolable por saber cada d\u00eda un poco m\u00e1s, contin\u00faa as\u00ed y no dejes que ese \u00e1nimo decaiga. Revisa el material complementario y realiza las actividades correspondientes. Te encuentro pr\u00f3ximamente.<\/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=ScR1T1DME14\" target=\"_blank\" rel=\"noreferrer noopener\">Unidad 10: Aut\u00f3matas Finitos, 0:06 \u2013 26:44.<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Introducci\u00f3n \u00a1Hola! Qu\u00e9 gusto poder encontrarte en esta nueva sesi\u00f3n, espero que sigas descubriendo este curso y lo sigas viendo fascinante. Por lo tanto, te doy la m\u00e1s cordial bienvenida a esta clase digital 6. En esta sesi\u00f3n aprenderemos sobre la teor\u00eda y antecedentes de los aut\u00f3matas finitos. Los aut\u00f3matas finitos son capaces de reconocer &#8230; <a title=\"Clase digital 6. An\u00e1lisis l\u00e9xico: Aut\u00f3matas de estado finito\" class=\"read-more\" href=\"https:\/\/blogs.ugto.mx\/rea\/clase-digital-6-analisis-lexico-automatas-de-estado-finito\/\" aria-label=\"Leer m\u00e1s sobre Clase digital 6. An\u00e1lisis l\u00e9xico: 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-16163","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\/16163","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=16163"}],"version-history":[{"count":5,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16163\/revisions"}],"predecessor-version":[{"id":19160,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16163\/revisions\/19160"}],"wp:attachment":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/media?parent=16163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/categories?post=16163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/tags?post=16163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}