{"id":6522,"date":"2018-07-09T10:53:19","date_gmt":"2018-07-09T09:53:19","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6522"},"modified":"2022-12-03T23:00:49","modified_gmt":"2022-12-03T22:00:49","slug":"resolution-par-le-lemme-darden","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/resolution-by-lemma-darden\/","title":{"rendered":"Solving by Arden's lemma"},"content":{"rendered":"
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tLanguage 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
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tHome 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
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tWiki<\/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
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\n\t\t\t\tDifficulty\t\t\t<\/span>\n\t\t\n\t\t
\n\t\t\t
\n\t\t\t\tHard<\/span>\n\t\t\t\t\t\t\t\t\t80%<\/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
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

Lemma of Arden<\/h2>\n

It is important to note that there are two symmetrical versions of Arden's lemma. Depending on the version you use, the method to generate the equations is slightly different.<\/p>\n\n

\"Arden<\/figure>\n\n

<\/span>Right version<\/span><\/h2>\n\n

Consider the following automaton:<\/p>\n\n

\"Arden<\/figure>\n\n

The construction of the equations is done as follows: the language recognized by a state is equal to the language followed by the transition symbol of its predecessors. For example, the language L2<\/sub> accepted by state 2 is equal to: L2<\/sub>\u00a0= L1<\/sub>To. A word w \u2208 Li<\/sub> if and only if he
exists a calculation of the automaton on w starting from the initial state and arriving in the state i (attention the version is not the same one on a left version).<\/p>\n\n

We have the following system of equation:<\/p>\n\n

\"Arden<\/figure>\n\n

By substituting L1<\/sub>\u00a0in the second equation by its value then L2<\/sub>\u00a0in the third and fourth equations we get:<\/p>\n\n

\"Arden<\/figure>\n\n

We apply the right Arden lemma to the last two equations:<\/p>\n\n

\"Arden<\/figure>\n\n

The language recognized by the automaton is the set of languages recognized by its terminal states, which in this example gives: ab (a + b) * + (b + aa) a *<\/p>\n\n

<\/span>Left version<\/span><\/h2>\n\n

Consider the following automaton:<\/p>\n\n

\"Arden<\/figure>\n\n

The construction of the equations is done as follows: the language recognized by a state is equal to the language preceded by the transition symbol of its successors. For example, the language L2<\/sub> accepted by state 2 is equal to: L2<\/sub>\u00a0= aL1<\/sub>+ aL3<\/sub>+ \u03b5 (because it is a terminal state). A word w \u2208 Li<\/sub>\u00a0if and only if he
exists a computation of the automaton on w starting from state i and arriving in a final state (be careful if we used the other version of the lemma, the definition would be different).<\/p>\n\n

We have the following system of equations:<\/p>\n\n

\"Arden<\/figure>\n\n

By substituting L3<\/sub>\u00a0and L4<\/sub>\u00a0in the first two equations then L2<\/sub>\u00a0in the first equation we get:<\/p>\n\n

\"Arden<\/figure>\n\n

Finally, by applying Arden's lemma (left version) to the first equation we
obtains: L1 = (a + bba + bbab) \u2217 (bb + \u03b5). Here we have the language recognized from the initial state, therefore from the automaton.<\/p>\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<\/div>","protected":false},"excerpt":{"rendered":"

Language Theory Wiki Home Difficulty Hard 80% Arden's Lemma It is important to note that there are two symmetrical versions of Arden's Lemma. Next \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-6522","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6522","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=6522"}],"version-history":[{"count":9,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6522\/revisions"}],"predecessor-version":[{"id":18643,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6522\/revisions\/18643"}],"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=6522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}