-
Notifications
You must be signed in to change notification settings - Fork 3
/
1-Vorspann_Sprachen.tex
153 lines (139 loc) · 6.93 KB
/
1-Vorspann_Sprachen.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
\section[Vorspann: Sprachen]{Vorspann: Sprachen\datenote{19.10.2018}}
\begin{Def}[name={[Alphabet $\Sigma$]}]
Ein \emph{Alphabet} ist eine nicht leere, endliche Menge von \emph{Zeichen}.
\end{Def} % 1.1
Zeichen sind hier beliebige abstrakte Symbole.
\newcommand{\aro}{\textit{rot}}
\newcommand{\age}{\textit{gelb}}
\newcommand{\agr}{\textit{grün}}
\begin{Bsp*} für Alphabete, die in dieser Vorlesung, im täglichem Umgang mit Computern oder in der Forschung an unserem Lehrstuhl eine Rolle spielen
\begin{itemize}
\item $\{a,\dots,z\}$
\item $\{0, 1\}$
\item $\{\aro, \age, \agr\}$ (Ampelfarben)
\item Die Menge aller ASCII-Symbole
\item Die Menge aller Statements eines Computerprogramms
\qedhere
\end{itemize}
\end{Bsp*}
Wir verwenden typischerweise den griechischen Buchstaben $\Sigma$ als Namen für ein Alphabet und die lateinischen Buchstaben $a,b,c$ als Namen für Zeichen.%
\footnote{Dies ist eine Konventionen analog zu den folgenden, die Sie möglicherweise in der Schule befolgten: Verwende $n,m$ für natürliche Zahlen. Verwende $\alpha, \beta$ für Winkel in Dreiecken. Verwende $A$ für Matrizen.}
Im Folgenden sei $\Sigma$ immer ein beliebiges Alphabet.%
\footnote{Dieser Satz dient dazu, dass die Autoren dieses Skripts nicht jede Definition mit ``Sei $\Sigma$ ein Alphabet...'' beginnen müssen.}
\begin{Def}[name={[Wort $w$ über $\Sigma$]}]\label{def:1.2}
Wir nennen eine endliche Folge von Elementen aus $\Sigma$ ein \emph{Wort}
und schreiben solch eine Folge immer ohne Trennsymbole wie z.B. Komma.\footnote{Wir schreiben also z.B. \texttt{einhorn} statt \texttt{e,i,n,h,o,r,n}.}
Die leere Folge nennen wir das \emph{leere Wort}; als Konvention stellen wir das leere Wort mit dem griechischen Buchstaben $\Eps$ dar.\footnote{Eine analoge Konvention, die sie aus der Schule kennen: Verwende immer $\pi$ als Symbol für die Kreiszahl.}
Wir bezeichnen die Menge aller Wörter mit $\Sigma^*$ und die Menge aller nicht leeren Wörter mit $\Sigma^+$.
Die \emph{Länge} eines Wortes, $|\cdot| : \Sigma^* \to \N$, ist die Anzahl der Elemente der Folge.
\end{Def}
Wir verwenden typischerweise $u,v,w$ als Namen für Wörter.
\goodbreak
\begin{Bsp*} für Wörter über $\Sigma=\{a,\dots,z\}$
\begin{itemize}
\item \verb/rambo/ (Länge $5$)
\item \verb/eis/, \verb/ies/ (beide Länge 3 aber ungleich)
\item $\Eps$ (Länge $0$)
\qedhere
\end{itemize}
\end{Bsp*}
Wörter lassen sich "`verketten''/"`hintereinanderreihen''.
Die entsprechende Operation heißt \emph{Konkatenation}, geschrieben "`$\cdot$'' (wie Multiplikation).
\begin{Def}[Konkatenation von Wörtern]
Die \emph{Konkatenation}, $\mathord{\cdot} : \Sigma^* \times \Sigma^* \to \Sigma^*$, ist für $u=u_1\ldots u_n\in\Sigma^*$ und $v=v_1\ldots v_m\in\Sigma^*$ definiert durch
$u\cdot v = u_1\ldots u_nv_1\ldots v_m$
% \begin{enumerate}
% \item $\Eps\cdot v = v$ (leeres Wort ist linksneutrales Element)
% \item $v\cdot \Eps = v$ (leeres Wort ist rechtsneutrales Element)
% \item $u\cdot (v \cdot w) = (u\cdot v) \cdot w$ (Assoziativität)
% \item $u(xw)\cdot v = ux(w\cdot v)$
% \end{enumerate}
\end{Def}
% Punkt 2 (rechtsneutrales Element) folgt bereits aus 1. und 3. und könnte auch weggelassen werden.
\begin{Bsp*} ~
\begin{itemize}
\item $\mathtt{eis}\cdot\mathtt{rambo} =\mathtt{eisrambo}$
\item $\mathtt{rambo} \cdot \Eps = \mathtt{rambo} = \Eps \cdot \mathtt{rambo}$
\qedhere
\end{itemize}
\end{Bsp*}
Eigenschaften von "`$\cdot$"':
\begin{itemize}
\item assoziativ
\item $\Eps$ ist neutrales Element
\item \emph{nicht} kommutativ
\end{itemize}
Der Konkatenationsoperator "`$\cdot$"' wird oft weggelassen (ähnlich wie der Multiplikationsoperator in der Arithmetik).
Ebenso können durch die Assoziativität Klammern weggelassen werden.
\begin{displaymath}
w_1w_2w_3 \;\; \text{ steht also auch für } \;\; w_1\cdot w_2\cdot w_3,\;\;\text{ für }\;\; (w_1 \cdot w_2) \cdot w_3 \;\;\text{ und für }\;\; w_1 \cdot (w_2 \cdot w_3)
\end{displaymath}
Bemerkung: Die Zeichenfolge \texttt{rambo}$\varepsilon$ ist \emph{kein} Wort.
Diese Zeichenfolge ist lediglich eine Notation für eine Konkatenationsoperation, die ein Wort der Länge 5 (nämlich \texttt{rambo}) beschreibt.
Wörter lassen sich außerdem \emph{potenzieren}:
\begin{Def}
Die \emph{Potenzierung} von Wörtern, $\cdot ^ \cdot: \Sigma^*\times \N \to \Sigma^*$, ist induktiv definiert durch
\begin{enumerate}
\item $w^0 = \Eps$
\item $w^{n+1} = w \cdot w^n$
\qedhere
\end{enumerate}
\end{Def}
\begin{Bsp*} $\mathtt{eis}^3
\stackrel{(2.)}{=} \mathtt{eis}\cdot\mathtt{eis}^2
\stackrel{\text{zweimal } (2.)}{=} \mathtt{eis}\cdot\mathtt{eis}\cdot\mathtt{eis}\cdot\mathtt{eis}^0
\stackrel{(1.)}{=} \mathtt{eis}\cdot\mathtt{eis}\cdot\mathtt{eis}\cdot\Eps
= \mathtt{eiseiseis}
$
\end{Bsp*}
\begin{Def}[name={[Sprache über $\Sigma$]}]
Eine \emph{Sprache} über $\Sigma$ ist eine Menge $L\subseteq\Sigma^*$.
\end{Def}
\goodbreak
\begin{Bsp*}~
\begin{itemize}
\item
$\{\mathtt{eis}, \mathtt{rambo}\}$
\item
$\{w\in\{0,1\}^*\mid w \text{ ist Binärcodierung einer Primzahl}\}$
\item $\{\}$ (die "`leere Sprache"')
\item $\{ \Eps \}$ (ist verschieden von der leeren Sprache)
\item $\Sigma^*$
\qedhere
\end{itemize}
\end{Bsp*}
Sämtliche Mengenoperationen sind auch Sprachoperationen, insbesondere Schnitt ($L_1 \cap L_2$), Vereinigung ($L_1 \cup L_2$), Differenz ($L_1 \setminus L_2$) und Komplement ($\overline{L_1} = \Sigma^* \setminus L_1$).
Weitere Operationen auf Sprachen sind Konkatenation und Potenzierung, sowie der \emph{Kleene-Abschluss}.
\begin{Def}[Konkatenation und Potenzierung von Sprachen] % 1.5
Seien $U,V\subseteq \Sigma^*$. Dann ist die \emph{Konkatenation} von $U$ und $V$ definiert durch
\[ U\cdot V = \{uv \mid u\in U, v\in V \} \]
und die \emph{Potenzierung} von $U$ induktiv definiert durch
\begin{enumerate}
\item $U^0 = \{\Eps\}$
\item $U^{n+1} = U \cdot U^{n}$
\qedhere
\end{enumerate}
\end{Def}
\begin{Bsp*}~
\begin{itemize}
\item $\{\mathtt{eis}, \Eps\} \cdot \{\mathtt{rambo}\} = \{\mathtt{eisrambo}, \mathtt{rambo}\}$
\item $\{\mathtt{eis}, \Eps\} \cdot \{\} = \{\}$
\item $\{\}^0 = \{\Eps\}$
\item $\{\}^4 = \{\}$
\item $\{\mathtt{eis}, \Eps\}^2 = \{\Eps, \mathtt{eis}, \mathtt{eiseis}\}$
\qedhere
\end{itemize}
\end{Bsp*}
Wie bei der Konkatenation von Wörtern dürfen wir den Konkatenationsoperator auch weglassen.
%
\begin{Def}[Kleene-Abschluss, Kleene-Stern, Kleene-Plus]
Gegeben eine Sprache $U\subseteq\Sigma^*$, definieren wir den \emph{Kleene-Abschluss} $U^*$ wie folgt.
$$U^* = \bigcup_{n\in\N} U^n$$
Wie nennen den Operator $\cdot^*: \mathcal{P}(\Sigma^*)\rightarrow\mathcal{P}(\Sigma^*)$ der für eine gegebene Sprache den Kleene-Abschluss liefert den \emph{Kleene-Stern}. Analog definieren wir den \emph{Kleene-Plus} Operator $\cdot^+: \mathcal{P}(\Sigma^*)\rightarrow\mathcal{P}(\Sigma^*)$ als
$$U^+ = \bigcup_{n\ge1} U^n.$$
\end{Def}
Es gilt also $U^*=U^+\cup\{\Eps\}$.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "Info_3_Skript_WS2016-17"
%%% End: