diff options
| -rw-r--r-- | notes-inf105.tex | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index a236c8b..054637f 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -221,7 +221,7 @@ les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in $x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$. À titre d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = -\{a,b,c,d\}$, et \texttt{foobar} est un mot (=chaîne de caractères) +\{a,b,c,d\}$, et \texttt{foobar} est un mot (= chaîne de caractères) sur l'alphabet ASCII. (Dans un contexte informatique, il est fréquent d'utiliser une sorte de guillemet pour délimiter les chaînes de caractères : on écrira donc \texttt{\char`\"foobar\char`\"} pour @@ -233,7 +233,7 @@ désigné $\Sigma^*$ (on verra en \ref{kleene-star} ci-dessous cette notation comme un cas particulier d'une construction « étoile » plus générale). Par exemple, si $\Sigma = \{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments sont toutes les suites finies -binaires (=suites finies de $0$ et de $1$). Ainsi, écrire « $w \in +binaires (= suites finies de $0$ et de $1$). Ainsi, écrire « $w \in \Sigma^*$ » signifie « $w$ est un mot sur l'alphabet $\Sigma$ ». {\footnotesize\thingy Typographiquement, on essaiera autant que @@ -500,7 +500,7 @@ l'alphabet).\par} \thingy Un \defin{langage} $L$ sur l'alphabet $\Sigma$ est simplement un ensemble de mots sur $\Sigma$. Autrement dit, il s'agit d'un -sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ (de tous les mots +sous-ensemble (= une partie) de l'ensemble $\Sigma^*$ (de tous les mots sur $\Sigma$) : en symboles, $L \subseteq \Sigma^*$. On souligne qu'on ne demande pas que $L$ soit fini (mais il peut @@ -522,10 +522,10 @@ Voici quelques autres exemples de langages : en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal exactement $3^{42}$. \item Le langage constitué des mots de longueur exactement $1$ sur un - alphabet $\Sigma$ (=mots de une seule lettre), qu'on peut identifier + alphabet $\Sigma$ (= mots de une seule lettre), qu'on peut identifier à $\Sigma$ lui-même (en identifiant un mot de une lettre à la lettre en question, cf. \ref{convention-on-words-of-length-one}). -\item Le langage (fini) constitué du seul mot vide (=mot de longueur +\item Le langage (fini) constitué du seul mot vide (= mot de longueur exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$. Ce langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut). Il ne faut pas le confondre avec le suivant : @@ -4562,7 +4562,7 @@ plus généraux que les grammaires hors contexte. Les \defin[grammaire contextuelle]{grammaires contextuelles} (ou grammaires de \textbf{type 1}) sont définies par des règles du type $\gamma T \gamma' \rightarrow \gamma \alpha \gamma'$ où $T$ est un nonterminal, -et $\alpha,\gamma,\gamma'$ des pseudo-mots (=mots sur l'alphabet de +et $\alpha,\gamma,\gamma'$ des pseudo-mots (= mots sur l'alphabet de tous les symboles), c'est-à-dire des règles qui autorisent la réécriture d'un symbole $T$ en $\alpha$ mais uniquement s'il est entouré d'un certain contexte ($\gamma$ à gauche, $\gamma'$ à droite). |