1\u00b0) Introduction<\/span><\/strong><\/p>\n La communication entre les hommes a\u00a0lieu dans des langages naturels.<\/p>\n Ces derniers peuvent \u00eatre ambigus car le cerveau humain peut comprendre les subtilit\u00e9s de ces<\/p>\n langages, les non-dits...<\/p>\n Par contre la communication homme-machine doit\u00a0se faire dans un langage artificiel non<\/p>\n ambigu.<\/p>\n Exemple : Voici un sch\u00e9ma qui repr\u00e9sente\u00a0les niveaux de langage intervenant en<\/p>\n programmation PASCAL, CAML sont des langages compil\u00e9s : tout le source du programme est d'abord analys\u00e9<\/p>\n lexicalement, syntaxiquement, s\u00e9mantiquement, link\u00e9(ajout des librairies) puis traduit<\/p>\n compl\u00e9tement en p-code\u00a0avant d'\u00eatre ex\u00e9cut\u00e9.<\/p>\n BASIC est un langage interpr\u00e9t\u00e9 : les instructions sont traduites interactivement l'une apr\u00e8s<\/p>\n l'autre en langage machine.<\/p>\n 2\u00b0) D\u00e9finitions des notions d'alphabet, de mot et de langage.<\/span><\/strong><\/p>\n A - Notion d'alphabet<\/span><\/strong><\/p>\n Un alphabet $A$ est un ensemble fini de symboles ou d'\u00e9l\u00e9ments appel\u00e9 lettres ou caract\u00e8res.<\/p>\n B - Notion de mot<\/strong><\/span><\/p>\n Un mot est une suite\u00a0finie d'\u00e9l\u00e9ments\u00a0d'un alphabet A<\/p>\n Ex : le mot $u = u_1u_2.....u_n$ o\u00f9 $\\forall\u00a0i\u00a0\u2208\u00a0[|1,n|] \\ u_i\u00a0\\in\u00a0A$<\/p>\n Ce mot $u$ a une longueur $n$ que l'on note $|u| = n$<\/p>\n Soit $a$ un symbole de l'alphabet $A$ ,\u00a0une occurrence de $a$ dans le mot $u$ est un indice $i \\in\u00a0\u00a0[|1 ,\u00a0|u\u00a0|]$\u00a0tel que $a = u_i$.\u00a0On note $|u|_a$\u00a0le nombre d'occurrences du symbole a dans le mot u.<\/p>\n Ex : $A = \\{a ; b \\} ; u = ababa ;\u00a0|u|\u00a0= 5\u00a0;\u00a0|u|_a\u00a0= 3 ;\u00a0|u|_b\u00a0= 2$<\/p>\n l'ensemble des mots d\u00e9fini sur un alphabet $A$ se note $A^*$<\/p>\n La suite vide se note $\\varepsilon$\u00a0ou $1_A$\u00a0et s'appelle le mot vide sa longueur est $0$<\/p>\n On note $A_0$\u00a0l'ensemble des mots de longueur $0$ donc $A_0 = \\{\\varepsilon\\}$<\/p>\n $A_1$\u00a0= l'ensemble des mots ou cha\u00eenes de caract\u00e8res de longueur $1$.<\/p>\n $A_2\u00a0= A_1 \\times\u00a0A_1\u00a0=$ l'ensemble des mots ou cha\u00eenes de caract\u00e8res de longueur $2$<\/p>\n $\\cdots$<\/p>\n $A_n\u00a0= A_1\u00a0\\times A_1\u00a0\\times \\cdots \\times A_1$\u00a0l'ensemble des mots\u00a0ou cha\u00eenes de caract\u00e8res de longueur $n$<\/p>\n donc $A^* = A_0 \\cup A_1 \\cup A_2 \\cdots \\cup A_n \\cup \\cdots \u00a0=\\bigcup_{i \\in N} A_i$<\/p>\n On note $A^+ =\u00a0A_1 \\cup A_2 \\cdots \\cup A_n \\cup \\cdots \u00a0=\\bigcup_{i \\in N^*} A_i$\u00a0= l'ensemble des mots de longueur non\u00a0nulle donc $A^+= A^*- \\{\u03b5\\}$<\/p>\n C - L'op\u00e9ration de concat\u00e9nation<\/strong><\/span><\/p>\n On peut d\u00e9finir sur $A^*$\u00a0une loi de composition interne : la concat\u00e9nation not\u00e9e .<\/p>\n $\\forall u = u_1u_2 \\cdots u_n \\in A^* \\quad\u00a0\\forall v\u00a0=\u00a0v_1v_2 \\cdots v_m \\in A^*$<\/p>\n $u . v$ est le mot $u_1u_2 \\cdots u_nv_1v_2 \\cdots\u00a0v_m$<\/p>\n Th\u00e9or\u00e8me 1 :<\/strong><\/p>\n $(A^*, .)$ est un mono\u00efde<\/strong><\/p>\n d\u00e9monstration \u00a0:<\/em> Th\u00e9or\u00e8me 2 : <\/strong> D - Notions de pr\u00e9fixe ,de suffi<\/strong><\/span>xe et de facteur d'un mot<\/strong><\/span><\/p>\n On peut d\u00e9finir dans $A^*$\u00a0la relation suivante not\u00e9e $\\leq$ par<\/p>\n $\\forall u \\in A^* \\quad \\forall v \\in A^* \\quad u \\leq v$<\/p>\n s'il existe un mot $w$ tel\u00a0que $v = u . w$<\/p>\n ( on dit alors que $u$ est un\u00a0pr\u00e9fixe\u00a0de $v$)<\/p>\n Th\u00e9or\u00e8me 3<\/strong><\/p>\n $\\leq$\u00a0<\/strong>est une relation d'ordre partiel dans $A^*$<\/strong><\/p>\n d\u00e9monstration :<\/em><\/p>\n Cette relation est alors une relation d'ordre. Cet ordre est partiel car il existe des\u00a0couples de mots $u$ et $v$ tels que $u$ n'est pas pr\u00e9fixe de $v$ et $v$ n'est pas pr\u00e9fixe de $u$.<\/p>\n Soit $u \\in A^*$ et soit $v \\in A^*$\u00a0on dit alors que $u$ est un\u00a0suffixe de $v$ s'il existe un mot $w$ tel que $v = w . u$<\/p>\n Soit $u\\in A^*$ et soit $v \\in A^*$\u00a0on dit alors que $u$ est un facteur\u00a0de $v$ s'il existe des mot $w$ et $t$ tels que $v = t . u . w$. Toutes les lettres de $u$ se retrouvent cons\u00e9cutivement dans $v$ et dans le m\u00eame\u00a0ordre.<\/p>\n Ex : $u = 0011$ est un facteur de $v = 0100110$. $101$ \u00a0n'est ni pr\u00e9fixe, ni suffixe de $v$.<\/p>\n $u = 00000$ est un sous-mot de $v\u00a0= 0100110101$ mais n'est pas un facteur de $v$<\/p>\n E - La notion de langage<\/strong><\/span><\/p>\n a) D\u00e9finition<\/span><\/strong><\/p>\n Un langage $L$ d\u00e9fini sur l'alphabet\u00a0A est un sous-ensemble (ou une partie) de\u00a0l'ensemble $A^*$\u00a0des mots<\/p>\n Un langage pourra \u00eatre d\u00e9fini :<\/p>\n - soit en\u00a0extension : on donne la liste de tous ses \u00e9l\u00e9ments<\/p>\n - soit encompr\u00e9hension : on donne une propri\u00e9t\u00e9 caract\u00e9ristique b)Remarque :<\/span><\/strong><\/p>\n Un langage $L \\in \\mathcal{P}(A^*)$. Or $\\emptyset \\subset A^*$\u00a0donc\u00a0$\\emptyset \\in \\mathcal{P}(A^*)$\u00a0donc\u00a0$\\emptyset$\u00a0est donc un\u00a0langage n'ayant aucun mot. c)\u00a0Exemples : d)\u00a0Op\u00e9rations sur les langages d\u00e9finis sur le m\u00eame alphabet A<\/span> <\/strong>:<\/p>\n Un langage fini peut \u00eatre d\u00e9crit par\u00a0l'\u00e9num\u00e9ration des mots qui le composent<\/p>\n Un langage infini peut \u00eatre d\u00e9crit par l'application d'op\u00e9rations sur des langages plus<\/p>\n simples ou par un ensemble de\u00a0r\u00e8gles qui forment une grammaire.<\/p>\n Certains langages infinis ne peuvent pas \u00eatre\u00a0d\u00e9finis par les 2 moyens pr\u00e9c\u00e9dents. On dit<\/p>\n alors qu'ils sont ind\u00e9cidables.<\/p>\n Une expression r\u00e9guli\u00e8re sur un alphabet $A$ est une formule de longueur finie<\/span><\/strong><\/p>\n correctement parenth\u00e9s\u00e9e utilisant uniquement les op\u00e9rations :<\/span><\/strong> On notera $\\{\u03b5\\} :\u00a0\u03b5$\u00a0et $\\{x\\} : x$ pour all\u00e9ger les notations.<\/p>\n Un langage est dit r\u00e9gulier lorsqu'il peut\u00a0\u00eatre d\u00e9crit par au moins une expression<\/span><\/strong><\/p>\n r\u00e9guli\u00e8re.<\/span><\/strong><\/p>\n L'ensemble des langages r\u00e9guliers sur A est stable pour les op\u00e9rations d'union, deconcat\u00e9nation et d'\u00e9toile. D'apr\u00e8s le Th\u00e9or\u00e8mede Kleene, il est aussi stable pour les op\u00e9rations d'intersection et de compl\u00e9mentarit\u00e9.<\/strong><\/span><\/p>\n","protected":false},"excerpt":{"rendered":" LES AUTOMATES ET LES LANGAGES 1\u00b0) Introduction La communication entre les hommes a\u00a0lieu dans des langages naturels. Ces derniers peuvent \u00eatre ambigus car le cerveau humain peut comprendre les subtilit\u00e9s de ces langages, les non-dits... Par contre la communication homme-machine doit\u00a0se faire dans un langage artificiel non ambigu. Exemple : Voici un sch\u00e9ma qui … Continuer la lecture de « Alphabets, mots et langages »<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"class_list":["post-931","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/931","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/comments?post=931"}],"version-history":[{"count":13,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/931\/revisions"}],"predecessor-version":[{"id":3429,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/931\/revisions\/3429"}],"wp:attachment":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/media?parent=931"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n![\"\"](\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/langages-300x176.png\")
<\/p>\n
\n. est une loi interne ;\u00a0. est associative ;\u00a0. admet un \u00e9l\u00e9ment neutre dans pour . c'est $\\varepsilon$<\/p>\n
\nTout mot s'\u00e9crit de fa\u00e7on unique comme\u00a0la concat\u00e9nation de mots de longueur 1<\/strong><\/p>\n\n
\n
\n
\nUn langage sera d\u00e9crit par une grammaire\u00a0qui permettra de construire une proc\u00e9dure\u00a0effective appel\u00e9e automate nous permettant de\u00a0d\u00e9cider si un mot fait ou non partie d'unlangage.
\nIl y a plusieurs classes de langages correspondant \u00e0 diff\u00e9rentes classes de grammaires\u00a0et d'automates.
\nPar exemple, les langages r\u00e9guliers correspondant aux grammaires r\u00e9guli\u00e8res et auxautomates d'\u00e9tats finis.
\nIls\u00a0sont fort utiles pour d\u00e9crire les entit\u00e9s lexicales deslangages de programmation.
\nLes langages hors-contexte correspondent\u00a0aux grammaires hors-contexte et aux\u00a0automates \u00e0 piles. Ils sont\u00a0fort utiles pour d\u00e9crire la syntaxe des langages de\u00a0programmation.<\/p>\n
\nIl ne\u00a0faut pas le confondre avec {\u03b5} ou {1_A}<\/p>\n
\n<\/strong><\/span>Ex 1<\/strong>
\nPour $A = {0 ; 1}$ alors $A^* = {0 ; 1}^*$ ; $L = {0^n1^n \/n \\in N}$\u00a0\u00a0form\u00e9 de la concat\u00e9nation de n \"z\u00e9ros\"suivis de n \"un\".
\nPar convention $0^01^0$\u00a0est le mot vide $\\varepsilon$.
\nEx 2
\n<\/strong>Pour $A = {0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 } \\cup\u00a0{ E ; -; . }$
\nOn peut alors cr\u00e9er en Pascal\u00a0des mots qui seront appel\u00e9s des r\u00e9els.
\nPar\u00a0exemple, $-65.3$ ou $127 E-3$ sont des r\u00e9els.<\/p>\n\n
\nExemple : si $A ={a}$ alors\u00a0$L^{\\leq 3} = {\\varepsilon,a,aa,aaa}$<\/li>\n
\n$L^* \\neq \\emptyset$\u00a0car m\u00eame si $L = \\emptyset$ car $\\emptyset^* = {\u03b5}<\/li>\n
\n- somme + \u00a0<\/span><\/strong>
\n- concat\u00e9nation .<\/span><\/strong>
\n\u00a0- \u00e9toile * <\/span><\/strong>
\nainsi que les langages $\\emptyset\u00a0, \\{\u03b5\\}$ et $\\{x\\}$ o\u00f9 x est une lettre quelconque de A.<\/span><\/strong><\/p>\n