2023-X-Ens-InfoFonda-MpMpi-Corrigé

Épreuve d’informatique fondamentale

Concision et ambiguïté

Le sujet porte sur les automates finis, dont la définition est rappelée dans le préambule. Le sujet s’intéresse à la propriété d’ambiguïté des automates finis, propriété également définie dans le préambule.

La première partie lie les notions de déterminisme et d’ambiguïté d’un automate fini en utilisant la notion de miroir d’un automate. La deuxième partie amène à définir un algorithme qui teste si un automate est ambigu et vous demande de déterminer sa complexité asymptotique.

La troisième et la quatrième partie étudient la concision des automates non ambigus et ambigus. Les parties 1 et 2 sont indépendantes ; il est conseillé de les traiter en premier car les parties 3 et 4 en dépendent.

Il est permis d’admettre les réponses à certaines questions pour répondre aux suivantes.

Préambule

On note {\Sigma} un alphabet fini, c’est à dire un ensemble fini de symboles appelés lettres. Un mot sur {\Sigma} est une suite finie de lettres.

On note {\Sigma^n} l’ensemble des mots de longueur n sur {\Sigma} et {\Sigma^\star} l’ensemble de tous les mots sur {\Sigma}. Soient u, v deux mots sur {\Sigma}, on note {u\cdot v} la concaténation de u et v. Un langage sur {\Sigma} est un sous-ensemble de {\Sigma^\star}.

Un automate sur {\Sigma} est un tuple {A=(Q,T,I,F)} où :

— Q est un ensemble fini de symboles appelés états ;

— {T\subseteq Q\times\Sigma\times Q} est appelé ensemble des transitions ;

— {I\subseteq Q} est l’ensemble des états initiaux ;

— {F\subseteq Q} est l’ensemble des états finaux. La Figure 1 représente graphiquement trois automates.

Les symboles dans Q sont encerclés, avec deux cercles pour les symboles dans F. Une transition {(q,a,q')\in T} est représentée par une flèche étiquetée par {a\in\Sigma}, allant de l’état source q à l’état destination {q'}. Les états initiaux sont indiqués par une flèche sans état source.

Un calcul de A sur un mot {w=a_0\ldots a_{n-1}\in\Sigma^\star} est une suite finie d’états {q_0\ldots q_n\in Q^\star} telle que {q_0\in I} et pour tout {i\lt n}, {(q_i,a_i,q_{i+1})\in T}. Un tel calcul est dit acceptant si {q_n\in F}. On dit alors que A accepte w. Le langage de A, noté L(A), est l’ensemble des mots acceptés par A.

Un automate A est dit déterministe si {|I|\leq1} et pour tout {(q,a)\in Q\times\Sigma}, {|\{q'\mid(q,a,q')\in T\}|\leq1.}Un automate A est dit complet si {|I|\geq1} et pour tout {(q,a)\in Q\times\Sigma}, {|\{q'\mid(q,a,q')\in T\}|\geq1}.

Figure 1 – Trois automates reconnaissant le même langage Soient {w\in\Sigma^\star} et A un automate.

Le mot w est dit ambigu pour A s’il existe deux calculs acceptants {\rho} et {\rho'} de A sur w avec {\rho\ne\rho'}. On définit {d_A(w)}, le degré d’ambiguïté de w dans A, comme étant le nombre de calculs acceptants différents de A sur w. Ainsi, w est ambigu pour A si et seulement si {d_A(w)>1}.

On note {\operatorname{Amb}(A)} l’ensemble des mots ambigus pour A. L’automate A est dit ambigu si {\operatorname{Amb}(A)\ne\varnothing}. Ce sujet s’intéresse tout particulièrement aux automates non ambigus.

1 Déterminisme et ambiguïté

Soit A un automate. On note {\widetilde A=(\widetilde Q,\widetilde T,\widetilde I,\widetilde F)} l’automate miroir de A, défini par :

— {\widetilde Q=Q} ;

— {\widetilde I=F} ;

— {\widetilde F=I} ;

— {\widetilde T=\{(t,a,s)\mid(s,a,t)\in T\}}. Un automate est dit co-déterministe si son automate miroir est déterministe.

2 Test d’ambiguïté

Le but de cette partie est d’obtenir un algorithme qui teste si un automate est ambigu et de déterminer sa complexité asymptotique. Dans cette partie, A est un automate (Q, T, I, F ) tel que {L(A)\ne\varnothing}.

2.1 Une construction utile

En utilisant A, on définit l’automate {\widehat A=(\widehat Q,\widehat T,\widehat I,\widehat F)} comme suit :

— {\widehat Q=Q\times Q\times\{0,1\}} ;

{\!\!\!\begin{array}{rl}—\;\widehat I&=\{(i,i,0)\mid i\in I\}\\[4pt]&\quad\cup\{(i,i',1)\mid i\in I,i'\in I,i\ne i'\}\end{array}} ;

— {\widehat F=\{(f,f',1)\mid f\in F,f'\in F\}} ;

— {\widehat T=T_1\cup T_2\cup T_3} avec : {\begin{array}{l}T_1=\{((s,s,0),a,(t,t,0))\mid(s,a,t)\in T\}\ ;\\[8pt]T_2=\{((s,s,0),a,(t,t',1))\mid\\[8pt]\quad(s,a,t)\in T,(s,a,t')\in T,t\ne t'\}\ ;\\[8pt]T_3=\{((s,s',1),a,(t,t',1))\mid\\[8pt]\quad(s,a,t)\in T,(s',a,t')\in T\}.\end{array}}

2.2 L’algorithme

Pour deux fonctions {f,g:\mathbb N\to\mathbb N}, on dit que g est une borne asymptotique de f, et on le note par {f\in O(g)}, s’il existe deux constantes strictement positives {n_0\in\mathbb N} et {c\in\mathbb N} telles que pour tout {n\geq n_0}, {f(n)\leq c\times g(n)}. Cette définition se généralise naturellement à des fonctions f et g avec plusieurs paramètres.

2.3 Généralisation

Soit k un entier strictement positif.

3 Concision des automates non ambigus

Le but de cette partie est de prouver que les automates non ambigus peuvent être exponentiellement plus concis que leurs équivalents déterministes et complets. Dans toute cette partie, on fixe l’alphabet {\Sigma=\{a,b\}}.

Pour {n\geq1} un entier, on pose {L_n=\{w_1\cdot b\cdot w_2\mid w_1,w_2\in\Sigma^\star,|w_2|=n-1\}}, le langage des mots dont la n-ième lettre en partant de la fin est un b.

On veut à présent prouver que tout automate déterministe et complet acceptant {L_n} a au moins {2^n} états.

Soit B un automate déterministe et complet et {w\in\Sigma^\star}. On note {q_w} l’état atteint par l’unique calcul de B sur w, c’est-à-dire l’état {q_m} tel que {q_0\ldots q_m} est un calcul de B sur w.

4 Concision des automates ambigus

Le but de cette partie est de prouver que les automates ambigus peuvent être exponentiellement plus concis que leurs équivalents non ambigus.

Pour {n\in\mathbb N}, on pose {\Sigma_n} un alphabet à n lettres et {K_n} le langage des mots sur {\Sigma_n^\star} dont au moins une lettre apparaît au moins deux fois, c’est-à-dire : {\begin{array}{l}K_n=\{w_1\cdot x\cdot w_2\cdot x\cdot w_3\mid\\[8pt]\quad w_1,w_2,w_3\in\Sigma_n^\star,x\in\Sigma_n\}.\end{array}}

On veut à présent prouver que tout automate non ambigu acceptant {K_n} a au moins {2^n+1} états. Jusqu’à la fin de cette partie, on fixe un entier {n\geq2} et un automate non ambigu {A=(Q,T,I,F)} acceptant {K_n}. Soient u et v deux mots de {\Sigma_n^\star}.

Lorsque {u\cdot v\in K_n}, on note {q_{u,v}} l’état de A atteint après avoir lu u lors de l’unique calcul acceptant de A sur {u\cdot v}. Autrement dit, soit {\ell=|u|} et {q_0\ldots q_m} l’unique calcul acceptant de A sur {u\cdot v}, alors {q_{u,v}=q_\ell}.

L’objectif à présent est de prouver que ces contraintes garantissent que A a au moins {2^n} états. Soit {s=(s_i)} une suite de mots et {\alpha} une lettre. On note {s\cdot\alpha} la suite {(s_i\cdot\alpha)}, c’est-à-dire la suite obtenue en ajoutant {\alpha} à la fin de chaque mot de s.

On fixe un ordre total {\lt} sur {\Sigma_n}, et on note {\Sigma_n=\{\alpha_1,\ldots,\alpha_n\}} avec pour tout {1\leq i\lt j\leq n}, {\alpha_i\lt\alpha_j}. On construit une famille {s^0,\ldots,s^n} de suites de mots de {\Sigma_n} comme suit :

— {s^0} est la suite contenant uniquement {\varepsilon} ;

— Pour {0\lt i\leq n}, {s^i=s^{i-1},s^{i-1}\cdot\alpha_i}, la suite constituée de {s^{i-1}}, suivie de la suite {s^{i-1}\cdot\alpha_i}.

Finalement, on pose {s=s^n}. Par exemple, pour n = 2, {\Sigma_2=\{a,b\}} et {a\lt b}, la suite s contient 4 éléments : {s_0=\varepsilon}, {s_1=a}, {s_2=b}, {s_3=ab}.

Finalement, on remarque que s contient {2^n} éléments et on pose {M_n} la matrice de dimension {2^n\times2^n} à coefficients en {\mathbb R} définie par : {M_n[i,j]=\begin{cases}1&\text{si }s_i\text{ et }s_j\text{ ont une lettre en commun}\\[8pt]0&\text{sinon.}\end{cases}}Par exemple, {M_2} est donnée ci-dessous : {M_2=\begin{pmatrix}0&0&0&0\\[8pt]0&1&0&1\\[8pt]0&0&1&1\\[8pt]0&1&1&1\end{pmatrix}}

À chaque état q de A, on associe le vecteur colonne {v_q} de dimension {2^n} défini par : {v_q[i]=\begin{cases}1&\text{s’il existe }j\lt2^n\text{ tel que }q=q_{s_i,s_j}\\[8pt]0&\text{sinon.}\end{cases}}