diff options
| -rw-r--r-- | notes-inf105.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 0cf4d2a..f60f754 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -4166,7 +4166,7 @@ ceux qui reconnaissent le langage rationnel $L$ : on l'appelle (automate)|see{minimal}}\textbf{automate canonique} du langage $L$. La démonstration ci-dessus en donne une construction à partir d'une relation d'équivalence, mais cette démonstration n'est pas -algorithmique : on va voir comment on peut le construire de fącon +algorithmique : on va voir comment on peut le construire de façon algorithmique à partir d'un DFA quelconque qui reconnaît $L$. \begin{prop}\label{dfa-minimization} @@ -5879,7 +5879,7 @@ cubique en la longueur de $w$. cherche pas simplement à savoir si un mot appartient au langage engendré par une grammaire, mais aussi à en construire un arbre d'analyse ; par ailleurs, la complexité algorithmique des approches -décrites en \ref{algebraic-languages-are-decidable} et meme +décrites en \ref{algebraic-languages-are-decidable} et même en \ref{handwaving-on-dynamical-programming} est inacceptable. En contrepartie de ces exigences, on est prêt à accepter de mettre des contraintes sur la grammaire qui la rendent plus facile à analyser : |