Provide a short (and very hastily written) argument for the decidability of algebraic languages.

1 files changed, 34 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 55990c8..a3e7fe5 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3838,6 +3838,40 @@ les automates à pile déterministes (qu'il faut définir soigneusement)
 acceptent strictement moins de langages que les automates à pile
 non déterministes.
 
+\thingy Une approche possible pour résoudre algorithmiquement,
+\emph{en théorie}, le problème de décider si un mot $w$ appartient au
+langage $L(G)$ engendré par une grammaire $G$ est la suivante :
+\begin{itemize}
+\item réécrire la grammaire (i.e., la remplacer par une grammaire
+  équivalente) de manière à ce que le membre de droite de chaque
+  production soit de longueur $\geq 2$, quitte à traiter spécialement
+  les éventuels mots de longueur $0$ et $1$ de $L(G)$,
+\item on a ensuite affaire à une grammaire \emph{monotone},
+  c'est-à-dire que l'application d'une règle ne peut qu'augmenter la
+  longueur du pseudo-mot en cours de dérivation, ce qui permet
+  d'explorer exhaustivement toutes les possibilités et de s'arrêter
+  dès qu'on dépasse la longueur $|w|$ à atteindre.
+\end{itemize}
+
+Pour ce qui est de la première partie : l'idée est d'éliminer d'abord
+les règles $T \rightarrow U$ (où $U$ est un nonterminal) : ces règles
+peuvent s'éliminer quitte à ajouter une règle $T \rightarrow \alpha$
+pour toute règle $U \rightarrow \alpha$ : on procède comme pour
+l'élimination des ε-transitions dans les εNFA (autrement dit, si on a
+une règle $V \rightarrow \alpha$ avec $V$ un nonterminal qui peut être
+dérivé par une suite de règles $T \rightarrow \cdots \rightarrow V$ en
+partant de $V$, on crée une règle $T \rightarrow \alpha$).  Ensuite,
+si on dispose de règles $T \rightarrow \varepsilon$ ou $T \rightarrow
+x$ (où $x$ est une lettre), on peut supprimer ces règles quitte à
+ajouter à chaque règle ayant un $T$ dans le membre de droite la même
+règle où $T$ a été remplacé par $\varepsilon$ ou $U$ ou $x$ selon le
+cas ; il faudra simplement faire un cas spécial, si $T$ est l'axiome
+de la grammaire, pour retenir que le mot $\varepsilon$ ou $x$ peut
+être produit.  À titre d'exemple, dans la grammaire $S \rightarrow
+aSbS \,|\, \varepsilon$, on peut écarter la règle $S \rightarrow
+\varepsilon$ quitte à ajouter des règles $S \rightarrow aSb$ et $S
+\rightarrow abS$ et $S \rightarrow ab$.
+