summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-09 17:54:49 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-09 17:54:49 +0100
commit38e7020031c298af453b1a383d0285e8a6f25d76 (patch)
treed17b72f591507e2a5302f93a3c13aff70ac01c99 /notes-inf105.tex
parentd0da92a1ce5565c8630896b2429b9d0b4dc812b6 (diff)
downloadinf105-38e7020031c298af453b1a383d0285e8a6f25d76.zip
inf105-38e7020031c298af453b1a383d0285e8a6f25d76.tar.gz
inf105-38e7020031c298af453b1a383d0285e8a6f25d76.tar.bz2
Mirror (=transpose) word, palindromes.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex12
1 files changed, 12 insertions, 0 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index e503f19..5ed7719 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -336,6 +336,18 @@ définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
\varepsilon$).
+\thingy Si $w = x_1\cdots x_n$, où $x_1,\ldots,x_n \in \Sigma$, est un
+mot de longueur $n$ sur un alphabet $\Sigma$, alors on définit son mot
+\textbf{miroir} ou \textbf{transposé}, parfois noté $w^{\textsf{R}}$
+ou $w^{\textsf{T}}$ (parfois les exposants sont écrits à gauche),
+comme le mot $x_n\cdots x_1$ dont les lettres sont les mêmes que
+celles de $w$ mais dans l'ordre inverse. À titre d'exemple,
+$(ababb)^{\textsf{R}} = bbaba$. On remarquera que $(w_1
+w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$
+sont deux mots quelconques.
+
+Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.
+
\subsection{Langages et opérations sur les langages}