From d3e561fe3210830f1bb640dede4fc3868b7d29dc Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 16 Jan 2017 16:53:44 +0100 Subject: Provide a short (and very hastily written) argument for the decidability of algebraic languages. --- notes-inf105.tex | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) 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$. + -- cgit v1.2.3