{"id":5028,"date":"2016-10-10T10:16:54","date_gmt":"2016-10-10T09:16:54","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=5028"},"modified":"2024-02-11T21:20:35","modified_gmt":"2024-02-11T20:20:35","slug":"theorie-des-langages","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/","title":{"rendered":"Teor\u00eda del lenguaje 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"5028\" class=\"elementor elementor-5028\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-51ff3d2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"51ff3d2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7f980ab\" data-id=\"7f980ab\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b912915 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b912915\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/2020\/04\/03\/teorias-y-algoritmos-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Teor\u00edas<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7682933\" data-id=\"7682933\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bb24cd7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"bb24cd7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-9b515d3\" data-id=\"9b515d3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d7c7978 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d7c7978\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Langage_formel\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7a609af elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7a609af\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fc436fe\" data-id=\"fc436fe\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-05878a6 elementor-widget elementor-widget-toggle\" data-id=\"05878a6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5791\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5791\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Idiomas, gram\u00e1ticas y aut\u00f3matas (teor\u00eda del lenguaje)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5791\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5791\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/tipos-de-gramaticas\/\">Tipos de gram\u00e1ticas<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/lenguajes-regulares-y-expresiones-regulares\/\">Lenguajes regulares y expresiones regulares<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/determinista-finito-automata\/\">Aut\u00f3mata finito determinista<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-finito-no-determinista\/\">Aut\u00f3mata finito indeterminista<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-con-transicion-vacia\/\">Aut\u00f3mata finito indeterminista con transici\u00f3n \u00e9psilon<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/automata-a-bateria\/\">Pushdown aut\u00f3mata y gram\u00e1tica fuera de contexto<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5792\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-5792\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Estudio de aut\u00f3matas<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5792\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-5792\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/construccion-de-thompson\/\">Aut\u00f3mata de Thompson<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/algoritmo-de-gloushkov\/\">Aut\u00f3mata de glushkov<\/a><\/li>\n<li>Optimizaci\u00f3n de Br\u00fcggemann-Klein<\/li>\n<li>Optimizaci\u00f3n de Chang-Paige<\/li>\n<li>Aut\u00f3mata antimirov<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/resolucion-por-lema-darden\/\">Lema de Arden<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5793\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-5793\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. C\u00e1lculo sobre aut\u00f3matas<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5793\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-5793\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/algoritmo-mcnaughton-y-yamada\/\">C\u00e1lculo de expresiones regulares por McNaughton y Yamada<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/algoritmo-brzozowski-y-mccluskey\/\">C\u00e1lculo de expresiones regulares por Brzozowski y McCluskey<\/a><\/li>\n<li>C\u00e1lculo de expresiones regulares por Conway<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/determinacion-afi-vers-afd\/\">Determinaci\u00f3n de AFI a AFD<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/determinacion-e-afi-vers-afd\/\">Determinaci\u00f3n de E-AFI a AFD<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/\">Minimizaci\u00f3n de un aut\u00f3mata determinista<\/a><\/li>\n<li>Uni\u00f3n, intersecci\u00f3n y complementariedad<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5794\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-5794\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Analizador<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5794\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-5794\"><ul>\n<li>LR<\/li>\n<li>LL<\/li>\n<li>SLR<\/li>\n<li>LALR<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-55a40483 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"55a40483\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-57673577\" data-id=\"57673577\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-17cecea7 elementor-widget elementor-widget-text-editor\" data-id=\"17cecea7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/#Theorie-des-langages\" >Teor\u00eda del lenguaje<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/#Alphabet\" >Alfabeto<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/#Langages\" >Idiomas<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/#Grammaire\" >Gram\u00e1tica<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Theorie-des-langages\"><\/span>Teor\u00eda del lenguaje<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: justify;\">En teor\u00eda del lenguaje, el conjunto de entidades elementales se llama alfabeto. Una combinaci\u00f3n de entidades elementales se llama palabra. Un conjunto de palabras se denomina idioma y se describe mediante una gram\u00e1tica. A partir de una gram\u00e1tica, podemos construir un procedimiento efectivo (llamado aut\u00f3mata) que permita decidir si una palabra es parte del lenguaje.<\/p>\n<p>Hay diferentes clases de lenguajes, correspondientes a diferentes clases de gram\u00e1ticas y aut\u00f3matas. Entre los m\u00e1s sencillos de estudiar, la clase de lenguajes regulares corresponde a gram\u00e1ticas regulares y aut\u00f3matas finitos. Esta clase de gram\u00e1tica se usa generalmente para describir la automatizaci\u00f3n del hogar sin ciclos.<\/p>\n<p>Una clase m\u00e1s global que los lenguajes regulares es la clase de lenguajes libres de contexto, correspondiente a gram\u00e1ticas libres de contexto y aut\u00f3matas pushdown. Esta clase de gram\u00e1tica, m\u00e1s poderosa que la clase de gram\u00e1ticas regulares, se usa t\u00edpicamente para la automatizaci\u00f3n del hogar con ciclos conocidos.<\/p>\n<p>La teor\u00eda del lenguaje es \u00fatil para:<\/p>\n<ul>\n<li>describir el comportamiento autom\u00e1tico (rob\u00f3tica, dom\u00f3tica, automatizaci\u00f3n de edificios)<\/li>\n<li>comprender todo un lenguaje y sus utilidades (compilador, ADN, aprendizaje autom\u00e1tico)<\/li>\n<li>Minimizar un proceso autom\u00e1tico (software integrado, tarjeta integrada para la industria aeroespacial o automotriz, etc.)<\/li>\n<\/ul>\n<h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Alphabet\"><\/span>Alfabeto<span class=\"ez-toc-section-end\"><\/span><\/h2>\nUn alfabeto, indicado A, es un conjunto finito no vac\u00edo de s\u00edmbolos (letras, signos, n\u00fameros, etc.)<\/p>\n<p>Una palabra, definida en un alfabeto A, es una secuencia finita de s\u00edmbolos \/ elementos de A.<\/p>\n\n<p style=\"text-align: justify;\"><img decoding=\"async\" class=\"aligncenter wp-image-6338 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage1.png\" alt=\"teor\u00eda del lenguaje\" width=\"517\" height=\"80\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage1.png 517w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage1-300x46.png 300w\" sizes=\"(max-width: 517px) 100vw, 517px\" \/><\/p>\n\n<p>Algunas propiedades de las palabras:<\/p>\n<ul>\n<li>La longitud de una palabra u definida en un alfabeto A, denotada por | u | es el n\u00famero de s\u00edmbolos (su cardinal) que componen u.<\/li>\n<li>| u |<sub>j<\/sub>\u00a0cuenta el n\u00famero de apariciones del s\u00edmbolo j en la palabra u.<\/li>\n<li>La palabra vac\u00eda, anotada \u03b5, se define en todos los alfabetos y es la palabra de longitud 0.<\/li>\n<li>El conjunto de todas las palabras formadas a partir del alfabeto A (resp. De todas las palabras no vac\u00edas) se denota con A<sup>*<\/sup>\u00a0(resp. A<sup>+<\/sup>).<\/li>\n<li>La concatenaci\u00f3n de dos palabras uyv, denotadas uv o uv, es la palabra formada siguiendo los s\u00edmbolos de u por los s\u00edmbolos de v. Una n potencia de una palabra es esta palabra concatenada n veces.<\/li>\n<li>si uno o m\u00e1s s\u00edmbolos est\u00e1n al poder + entonces significa que hay uno o m\u00e1s s\u00edmbolos de este tipo en la palabra (ej. (ab)<sup>+<\/sup>= ab\u2026)<\/li>\n<li>si uno o m\u00e1s s\u00edmbolos est\u00e1n a la potencia * entonces significa que hay cero o m\u00e1s s\u00edmbolos de este tipo en la palabra<\/li>\n<\/ul>\n\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-6339 size-full\" style=\"text-align: justify;\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage2.png\" alt=\"teor\u00eda del lenguaje\" width=\"529\" height=\"108\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage2.png 529w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage2-300x61.png 300w\" sizes=\"(max-width: 529px) 100vw, 529px\" \/><\/p>\n<p>Dejemos que dos palabras uyv se definan en un alfabeto A.<\/p>\n\n<li>u es un prefijo de v si y solo si existe una palabra w (potencialmente vac\u00eda) tal que uw = v.<\/li>\n<li>u es un sufijo de v si y solo si existe una palabra w (potencialmente vac\u00eda) tal que wu = v.<\/li>\n<li>u es un factor de v si y solo si hay dos palabras (potencialmente vac\u00edas) w<sub>1<\/sub>\u00a0y W<sub>2<\/sub>\u00a0como w<sub>1<\/sub>uw<sub>2<\/sub>= v.<\/li>\n<li>una palabra no vac\u00eda u se dice que es primitiva si la ecuaci\u00f3n u = v<sup>I<\/sup> no admite una soluci\u00f3n para i&gt; 1.<\/li>\n<li>dos palabras x = uv e y = vu deducidas entre s\u00ed por intercambio de prefijo y sufijo se dice que est\u00e1n conjugadas.<\/li>\n<\/ul>\n\n<h2><span class=\"ez-toc-section\" id=\"Langages\"><\/span>Idiomas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Un idioma, definido en un alfabeto A, es un conjunto de palabras definidas en A. Un idioma es un subconjunto de A<sup>*<\/sup>.<\/p>\n\nEstablecer operaciones definidas en idiomas:<br \/><img decoding=\"async\" class=\"aligncenter wp-image-6340 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage3.png\" alt=\"teor\u00eda del lenguaje\" width=\"317\" height=\"154\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage3.png 317w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/langage3-300x146.png 300w\" sizes=\"(max-width: 317px) 100vw, 317px\" \/>\n\n<ul>\n<li>La uni\u00f3n contiene todas las palabras que est\u00e1n contenidas en L<sub>1<\/sub> ya sea en L<sub>2<\/sub>.<\/li>\n<li>Intersecci\u00f3n es el lenguaje que contiene todas las palabras contenidas al mismo tiempo en L<sub>1<\/sub> y en L<sub>2<\/sub>.<\/li>\n<li>El complemento de un idioma es el idioma que contiene todas las palabras que no est\u00e1n en ese idioma.<\/li>\n<li>La diferencia entre dos idiomas es el idioma que contiene todas las palabras de L<sub>1<\/sub>\u00a0que no est\u00e1n en L<sub>2<\/sub>.<\/li>\n<\/ul>\n\n<p>Adem\u00e1s de establecer operaciones sobre idiomas, el producto o concatenaci\u00f3n de dos idiomas y definido por el idioma que contiene todas las palabras formadas a partir de la concatenaci\u00f3n de una palabra de L<sub>1<\/sub> seguido de una palabra de L<sub>2<\/sub>. El producto de las lenguas es asociativo pero no conmutativo.<\/p>\n<p>El poder de una lengua es una concatenaci\u00f3n sucesiva de esta lengua L<sup>no<\/sup>= LL<sup>n-1<\/sup>. El poder del 0 forma el lenguaje compuesto por la palabra vac\u00eda.<\/p>\n\nConsidere, por ejemplo, los dos idiomas L<sub>1<\/sub> = {00, 11} y L<sub>2<\/sub> = {0, 1, 01} establecido en {0,1}. l<sub>1<\/sub>.LOS<sub>2<\/sub> = {000, 001, 0001, 110, 111, 1101}.\n\n<h2><span class=\"ez-toc-section\" id=\"Grammaire\"><\/span>Gram\u00e1tica<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Un lenguaje puede describirse mediante un cierto n\u00famero de reglas: la gram\u00e1tica indica c\u00f3mo construir oraciones pertenecientes al lenguaje (operaci\u00f3n en producci\u00f3n); la gram\u00e1tica tambi\u00e9n permite decidir si una oraci\u00f3n determinada pertenece o no a la lengua (funcionamiento en reconocimiento).<\/p>\n\n<p>Una gram\u00e1tica es un cuatrillizo G = (T, N, S, R) tal que:<\/p>\n<ul>\n<li>T es el vocabulario terminal, es decir, el alfabeto en el que se define la lengua.<\/li>\n<li>N es el vocabulario no terminal, es decir, el conjunto de s\u00edmbolos que no aparecen en las palabras generadas, pero que se utilizan durante la generaci\u00f3n. Un s\u00edmbolo no terminal designa una categor\u00eda sint\u00e1ctica.<\/li>\n<li>R es un conjunto de las llamadas reglas de reescritura o producci\u00f3n de la forma: u1 \u2192 u2, con u1 \u2208 (N \u222a T)<sup>+<\/sup>\u00a0y u2 \u2208 (N \u222a)<sup>*<\/sup>. Recuerde que + significa al menos un elemento y * significa 0 o m\u00e1s. El significado intuitivo de estas reglas es que la serie no vac\u00eda de s\u00edmbolos terminales o no terminales u1 puede ser reemplazada posteriormente opcionalmente vac\u00eda de s\u00edmbolos terminales o no terminales u2.<\/li>\n<li>S \u2208 N es el s\u00edmbolo o axioma inicial. Es a partir de este s\u00edmbolo no terminal que comenzaremos la generaci\u00f3n de palabras mediante las reglas de la gram\u00e1tica.<\/li>\n<\/ul>\n\n<p>Cuando varias reglas gramaticales tienen la misma forma en la parte izquierda,<br \/>podr\u00e1 factorizar estas diferentes reglas separando las partes rectas por l\u00edneas verticales. Por ejemplo, el conjunto de reglas S \u2192 ab, S \u2192 aSb, S \u2192 c podr\u00eda escribirse S \u2192 ab | aSb | vs.<\/p>\n<p>El lenguaje definido o generado por una gram\u00e1tica es el conjunto de palabras que se pueden obtener del s\u00edmbolo inicial aplicando las reglas de la gram\u00e1tica. M\u00e1s formalmente, introducimos las nociones de derivaci\u00f3n entre formas, esta consiste en reemplazar un s\u00edmbolo no terminal por una serie de s\u00edmbolos terminales y no terminales seg\u00fan las reglas gramaticales.<\/p>\n<p>Para obtener informaci\u00f3n adicional sobre las operaciones entre el lenguaje y la gram\u00e1tica, consulte la tabla de enlaces en la parte superior de este curso.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Teor\u00edas P\u00e1gina principal Wiki I. Lenguajes, gram\u00e1ticas y aut\u00f3matas (teor\u00eda de los lenguajes) Tipos de gram\u00e1ticas Lenguajes regulares y expresiones regulares Aut\u00f3mata finito determinista Aut\u00f3mata finito\u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5028","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/5028","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=5028"}],"version-history":[{"count":25,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/5028\/revisions"}],"predecessor-version":[{"id":20464,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/5028\/revisions\/20464"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=5028"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}