summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-16 16:53:44 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-16 16:53:44 +0100
commitd3e561fe3210830f1bb640dede4fc3868b7d29dc (patch)
tree67d1af5caaf4cf4612c298203d62ed878e43e205
parentb58c7150c57b62c3fed7b705ff38b26487a5b3c1 (diff)
downloadinf105-d3e561fe3210830f1bb640dede4fc3868b7d29dc.tar.gz
inf105-d3e561fe3210830f1bb640dede4fc3868b7d29dc.tar.bz2
inf105-d3e561fe3210830f1bb640dede4fc3868b7d29dc.zip
Provide a short (and very hastily written) argument for the decidability of algebraic languages.
-rw-r--r--notes-inf105.tex34
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$.
+