{"id":6342,"date":"2018-05-28T10:15:52","date_gmt":"2018-05-28T09:15:52","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6342"},"modified":"2022-12-03T23:00:29","modified_gmt":"2022-12-03T22:00:29","slug":"types-de-grammaires","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/types-of-grammars\/","title":{"rendered":"Types of grammars"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6342\" class=\"elementor elementor-6342\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-eda172b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eda172b\" 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-fab53f4\" data-id=\"fab53f4\" 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-d70288d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d70288d\" 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\/language-theory\/\">\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\">Language theory<\/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-989ae5b\" data-id=\"989ae5b\" 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-1abb58e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1abb58e\" 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-b621b5f\" data-id=\"b621b5f\" 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-2bb333a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2bb333a\" 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\/Grammaire_formelle\" 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-f95ec4b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f95ec4b\" 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-8bb897d\" data-id=\"8bb897d\" 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-19c5d0d elementor-widget elementor-widget-progress\" data-id=\"19c5d0d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"progress.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<span class=\"elementor-title\" id=\"elementor-progress-bar-19c5d0d\">\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t<div aria-labelledby=\"elementor-progress-bar-19c5d0d\" class=\"elementor-progress-wrapper\" role=\"progressbar\" aria-valuemin=\"0\" aria-valuemax=\"100\" aria-valuenow=\"80\" aria-valuetext=\"80% (Difficile)\">\n\t\t\t<div class=\"elementor-progress-bar\" data-max=\"80\">\n\t\t\t\t<span class=\"elementor-progress-text\">Hard<\/span>\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-progress-percentage\">80%<\/span>\n\t\t\t\t\t\t\t<\/div>\n\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-53f7b734 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"53f7b734\" 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-7eddd68f\" data-id=\"7eddd68f\" 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-5e1762cd elementor-widget elementor-widget-text-editor\" data-id=\"5e1762cd\" 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\/types-of-grammars\/#Grammaires\" >Grammars<\/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\/types-of-grammars\/#Classification-de-Chomsky\" >Chomsky classification<\/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\/types-of-grammars\/#Exemple-1\" >Example 1<\/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\/types-of-grammars\/#Exemple-2\" >Example 2<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Grammaires\"><\/span>Grammars<span class=\"ez-toc-section-end\"><\/span><\/h2><p>By introducing more or less restrictive criteria on the form of the grammar rules, we obtain hierarchical grammar classes (types of grammars), ordered by inclusion. The classification of grammars, defined in 1957 by Noam Chomsky, distinguishes four classes.<\/p><h2><span class=\"ez-toc-section\" id=\"Classification-de-Chomsky\"><\/span>Chomsky classification<span class=\"ez-toc-section-end\"><\/span><\/h2><p><strong>Type 0:<\/strong> no restriction on the rules.<\/p><p><strong>Type 1:<\/strong> context sensitive or contextual grammars. The rules of R are of the form:<\/p><ul><li>uAv \u2192 uwv with A \u2208 N, u, v \u2208 (N \u222a T)<sup>\u2217\u00a0<\/sup>and w \u2208 (N \u222a T)<sup>+<\/sup><\/li><li>In other words, the non-terminal symbol A is replaced by w if we have the contexts u on the left and v on the right.<\/li><\/ul><p><strong>Type 2:<\/strong> context-free grammars. The rules of R are of the form:<\/p><ul><li>A \u2192 w with A \u2208 N and w \u2208 (N \u222a T)<sup>\u2217<\/sup><\/li><li>In other words, the left side of each rule consists of a single non-terminal symbol.<\/li><\/ul><p><strong>Type 3:<\/strong> regular grammars<\/p><ul><li>\u00a0to the right. The rules of R are of the form<br \/>A \u2192 aB or A \u2192 a with A, B \u2208 N and a \u2208 T<\/li><li>to the left. The rules of R are of the form<br \/>A \u2192 Ba or A \u2192 a with A, B \u2208 N and a \u2208 T<\/li><li>In other words, the left side of each rule consists of a single non-terminal symbol, and the right side consists of a terminal symbol and possibly a non-terminal symbol. For regular grammars on the right, the non-terminal symbol must always be to the right of the terminal symbol while for regular grammars on the left it must be on the left.<\/li><\/ul><h2><span class=\"ez-toc-section\" id=\"Exemple-1\"><\/span>Example 1<span class=\"ez-toc-section-end\"><\/span><\/h2><p>We consider the language L of words on {0, 1} which represent even unsigned base 2 integers (the words of this language all end with 0 and do not start with 0, except for the zero integer). Formally define L and construct a regular grammar describing L.<\/p><p>The language is of the following form: L = {0, 1u0 \/ u \u2208 {0, 1}<sup>\u2217<\/sup>}<\/p><p>We define the regular right-hand grammar G = (T, N, S, R) where<br \/>T = {0, 1}<br \/>N = {S, U}<br \/>R = {S \u2192 0 | 1U<br \/>U \u2192 1U | 0U | 0}<br \/>as well as the regular left grammar G = (T, N, S, R) where<br \/>T = {0, 1}<br \/>N = {S, U}<br \/>R = {S \u2192 0 | U0<br \/>U \u2192 U1 | U0 | 1}<\/p><p>Preferably, we always take the regular right-hand grammar for the study of future states in automata.<\/p><h2><span class=\"ez-toc-section\" id=\"Exemple-2\"><\/span>Example 2<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Here are the grammar productions: P \u2192 aP, P \u2192 aQ, Q \u2192 bP, Q \u2192 R, R \u2192 bR, R \u2192 cQ, R \u2192 bP, R \u2192 \u03b5. The non-terminals of the grammar are {P, Q, R}, the initial symbol is P.<\/p><p>By denoting with X<sub>p<\/sub>, X<sub>q<\/sub>, X<sub>r<\/sub> the languages accepted from the states P, Q and R respectively, the system of equations for these languages is:<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6344 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/grammair1.png\" alt=\"grammar\" width=\"534\" height=\"468\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/grammair1.png 534w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/05\/grammair1-300x263.png 300w\" sizes=\"(max-width: 534px) 100vw, 534px\" \/><\/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>Theory of languages Home page Wiki Difficulty Difficult 80% Grammars By introducing more or less restrictive criteria on the form of grammar rules, \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":5028,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-6342","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6342","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=6342"}],"version-history":[{"count":2,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6342\/revisions"}],"predecessor-version":[{"id":18581,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6342\/revisions\/18581"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}