{"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\/en\/language-theory\/","title":{"rendered":"Language Theory 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\/en\/2020\/04\/03\/theories-and-algorithms-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\">Theories<\/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\/en\/\">\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\">Home page<\/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. Languages, grammars and automata (language theory)<\/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\/en\/language-theory\/types-of-grammars\/\">Types of grammars<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/regular-languages-and-regular-expressions\/\">Regular languages and regular expressions<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/deterministic-finite-automaton\/\">Deterministic finite automaton<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/non-deterministic-finite-automaton\/\">Indeterministic finite automaton<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/automaton-with-empty-transition\/\">Indeterministic finite automaton with epsilon transition<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/battery-powered-automaton\/\">Pushdown automaton and grammar out of context<\/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. Study of automatons<\/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\/en\/language-theory\/construction-of-thompson\/\">Thompson&#039;s automaton<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/gloushkov-algorithm\/\">Glushkov automaton<\/a><\/li>\n<li>Br\u00fcggemann-Klein optimization<\/li>\n<li>Chang-Paige optimization<\/li>\n<li>Antimirov automaton<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/resolution-by-lemma-darden\/\">Lemma of 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. Calculation on automata<\/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\/en\/language-theory\/mcnaughton-and-yamada-algorithm\/\">Regular expression calculation by McNaughton and Yamada<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/brzozowski-and-mccluskey-algorithm\/\">Regular expression calculation by Brzozowski and McCluskey<\/a><\/li>\n<li>Regular expression calculation by Conway<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/determinization-afi-vers-afd\/\">AFI to AFD determination<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/determinization-e-afi-vers-afd\/\">E-AFI to AFD determination<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/minimization-dun-afd\/\">Minimization of a deterministic automaton<\/a><\/li>\n<li>Union, intersection and complementary<\/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. Parser<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/language-theory\/#Theorie-des-langages\" >Language theory<\/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\/en\/language-theory\/#Alphabet\" >Alphabet<\/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\/en\/language-theory\/#Langages\" >Languages<\/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\/en\/language-theory\/#Grammaire\" >Grammar<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Theorie-des-langages\"><\/span>Language theory<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: justify;\">In language theory, the set of elementary entities is called the alphabet. A combination of elementary entities is called a word. A set of words is called a language and is described by a grammar. From a grammar, we can build an effective procedure (called automaton) allowing to decide if a word is part of the language.<\/p>\n<p>There are different classes of languages, corresponding to different classes of grammars and automata. Among the simplest to study, the class of regular languages corresponds to regular grammars and finite automata. This grammar class is typically used to describe cycleless home automation.<\/p>\n<p>A more global class than regular languages is the class of context-free languages, corresponding to context-free grammars and pushdown automata. This class of grammar, more powerful than the class of regular grammars, is typically used for home automation with known cycles.<\/p>\n<p>Language theory is useful for:<\/p>\n<ul>\n<li>describe automatic behavior (robotics, home automation, building automation)<\/li>\n<li>understand all of a language and its utilities (compiler, DNA, machine learning)<\/li>\n<li>Minimize an automatic process (integrated software, integrated card for the aerospace or automotive industry, etc.)<\/li>\n<\/ul>\n<h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Alphabet\"><\/span>Alphabet<span class=\"ez-toc-section-end\"><\/span><\/h2>\nAn alphabet, noted A, is a finite non-empty set of symbols (letters, signs, numbers, etc.)<\/p>\n<p>A word, defined on an alphabet A, is a finite sequence of symbols \/ elements of 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=\"language theory\" 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>Some properties on words:<\/p>\n<ul>\n<li>The length of a word u defined on an alphabet A, denoted by | u | is the number of symbols (its cardinal) that make up u.<\/li>\n<li>| u |<sub>j<\/sub>\u00a0counts the number of occurrences of the symbol j in the word u.<\/li>\n<li>The empty word, noted \u03b5, is defined on all alphabets and is the word of length 0.<\/li>\n<li>The set of all the words formed from the alphabet A (resp. Of all the nonempty words) is denoted by A<sup>*<\/sup>\u00a0(resp. A<sup>+<\/sup>).<\/li>\n<li>The concatenation of two words u and v, denoted uv or uv, is the word formed by following the symbols of u by the symbols of v. An n power of a word is this word concatenated n times.<\/li>\n<li>if one or more symbols is to the power + then it means that there is one or more symbol of this type in the word (ex. (ab)<sup>+<\/sup>= ab\u2026)<\/li>\n<li>if one or more symbols is to the power * then it means that there is zero or more symbol of this type in the word<\/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=\"language theory\" 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>Let two words u and v be defined on an alphabet A.<\/p>\n\n<li>u is a prefix of v if and only if there exists a (potentially empty) word w such that uw = v.<\/li>\n<li>u is a suffix of v if and only if there exists a (potentially empty) word w such that wu = v.<\/li>\n<li>u is a factor of v if and only if there are two (potentially empty) words w<sub>1<\/sub>\u00a0and w<sub>2<\/sub>\u00a0such as w<sub>1<\/sub>uw<sub>2<\/sub>= v.<\/li>\n<li>a non-empty word u is said to be primitive if the equation u = v<sup>i<\/sup> does not admit a solution for i&gt; 1.<\/li>\n<li>two words x = uv and y = vu deduced from each other by exchange of prefix and suffix are said to be conjugated.<\/li>\n<\/ul>\n\n<h2><span class=\"ez-toc-section\" id=\"Langages\"><\/span>Languages<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A language, defined on an alphabet A, is a set of words defined on A. A language is a subset of A<sup>*<\/sup>.<\/p>\n\nSet operations defined on languages:<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=\"language theory\" 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>The union contains all the words that are either contained in L<sub>1<\/sub> either in L<sub>2<\/sub>.<\/li>\n<li>Intersection is the language which contains all the words contained at the same time in L<sub>1<\/sub> and in L<sub>2<\/sub>.<\/li>\n<li>The complement of a language is the language containing all the words that are not in that language.<\/li>\n<li>The difference between two languages is the language containing all the words of L<sub>1<\/sub>\u00a0which are not in L<sub>2<\/sub>.<\/li>\n<\/ul>\n\n<p>In addition to set operations on languages, the product or concatenation of two languages and defined by the language containing all the words formed from the concatenation of a word of L<sub>1<\/sub> followed by a word of L<sub>2<\/sub>. The product of languages is associative but not commutative.<\/p>\n<p>The power of a language is a successive concatenation of this language L<sup>not<\/sup>= LL<sup>n-1<\/sup>. The power of 0 forms the language composed of the empty word.<\/p>\n\nConsider for example the two languages L<sub>1<\/sub> = {00, 11} and L<sub>2<\/sub> = {0, 1, 01} set to {0,1}. L<sub>1<\/sub>.THE<sub>2<\/sub> = {000, 001, 0001, 110, 111, 1101}.\n\n<h2><span class=\"ez-toc-section\" id=\"Grammaire\"><\/span>Grammar<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A language can be described by a certain number of rules: the grammar indicates how to construct sentences belonging to the language (operation in production); the grammar also makes it possible to decide whether or not a given sentence belongs to the language (functioning in recognition).<\/p>\n\n<p>A grammar is a quadruplet G = (T, N, S, R) such that:<\/p>\n<ul>\n<li>T is the terminal vocabulary, that is to say the alphabet on which the language is defined.<\/li>\n<li>N is the non-terminal vocabulary, that is to say the set of symbols which do not appear in the generated words, but which are used during the generation. A non-terminal symbol designates a syntactic category.<\/li>\n<li>R is a set of so-called rewriting or production rules of the form: u1 \u2192 u2, with u1 \u2208 (N \u222a T)<sup>+<\/sup>\u00a0and u2 \u2208 (N \u222a)<sup>*<\/sup>. Recall that + means at least one element, and * means 0 or more. The intuitive meaning of these rules is that the non-empty series of terminal or non-terminal symbols u1 can subsequently be replaced optionally empty of terminal or non-terminal symbols u2.<\/li>\n<li>S \u2208 N is the starting symbol or axiom. It is from this non-terminal symbol that we will start the generation of words by means of the rules of grammar.<\/li>\n<\/ul>\n\n<p>When several grammar rules have the same form in the left part, we<br \/>can factorize these different rules by separating the straight parts by vertical lines. For example, the set of rules S \u2192 ab, S \u2192 aSb, S \u2192 c could be written S \u2192 ab | aSb | vs.<\/p>\n<p>The language defined, or generated, by a grammar is the set of words which can be obtained from the starting symbol by applying the rules of grammar. More formally, we introduce the notions of derivation between forms, this consists in replacing a non-terminal symbol by a series of terminal and non-terminal symbols according to the grammar rules.<\/p>\n<p>For additional information on operations between language and grammar, please refer to the links table at the top of this course.<\/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>Theories Home page Wiki I. Languages, grammars and automata (theory of languages) Types of grammars Regular languages and regular expressions Deterministic finite automaton Finite automata \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\/en\/wp-json\/wp\/v2\/pages\/5028","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=5028"}],"version-history":[{"count":25,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028\/revisions"}],"predecessor-version":[{"id":20464,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028\/revisions\/20464"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=5028"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}