5.7 Übungsaufgaben

Reguläre Sprachen und primitive Rekursion

Übungsaufgabe 5.7.1 Sei $\Sigma = \{\sigma_1, \sigma_2, \dots, \sigma_k\}$ ein endliches Alphabet. Wir können jedes Zeichen $\sigma_i \in \Sigma$ als natürliche Zahl $i$ codieren. Ein Wort $\alpha \in \Sigma^*$ wird somit zu einer Folge $(a_1, a_2, \dots, a_n) \in \N^*$, was wir wiederum mit den Methoden aus Kapitel 2.2 als eine natürliche Zahl $\bar{\alpha}$ codieren können. Mittels dieser Codierung wird eine Sprache $L \subseteq \Sigma^*$ zu einer Funktion

\begin{align*} f_L : \N & \rightarrow \{0,1\} \ a & \mapsto

{\begin{cases} 1 & if \exists α \in L with \bar{α} = a \\ 0 & else. \end{cases}

Sei $L$ eine reguläre Sprache. Zeigen Sie, dass $f_L$ primitiv rekursiv ist!

\end{align*}

Reguläre Sprachen und Schaltkreise

Wir können jedes Zeichen $\sigma \in \Sigma$ als Bitstring $x_{\sigma} \in \cube^k$ codieren, mit $k = \ceil{\log_2|\Sigma|}$, und damit jedes $\alpha = (a_1, \dots, a_n) \in \Sigma^*$ als $x_a \in \cube^*$ mit $nk$ Bits. Smit wird jede Sprache $L \subseteq \Sigma^*$ zu einer Funktion $f_L : \cube^* \rightarrow \cube$ mittels

\begin{aligned} f_{L} : {0, 1}^{*} & \to {0, 1} \\ y & \mapsto {\begin{cases} 1 & if \exists α \in L : x_{α} = y \\ 0 & else. \end{cases} \end{aligned}

Für festes $n$ definieren wir $f_L^n : \cube^n \rightarrow \cube$ als die Restriktion von $f_L$ auf $\cube$, also die Funktion, die nur $n$-Bit-Strings als Input akzeptiert.

Zeigen Sie: wenn $L \subseteq \Sigma^*$ regulär ist, dann gibt es für jedes $n$ einen Schaltkreis $C$ mit $O(n)$ Gates, der $f_L$ berechnet.

Übungsaufgabe 5.7.2 Verbessern Sie die obige Konstruktion: Ihr Schaltkreis $C$ sollte nun Tiefe $O(\log(n))$ haben und vorzugsweise immer noch $O(n)$ Gates.

Übungsaufgabe 5.7.3 (Challenge). Betrachten wir eine Variante des endlichen Automaten, bei der der Automat zurückspulen kann. Der Automat hat also einen "Lesekopf", mit dem er auf einem Zeichen des Eingabewortes steht (anfangs auf dem ersten). In jedem Schritt kann er nach rechts oder links wechseln. Es gibt zwei spezielle Zeichen, die markieren, wo das Wort aufhört: $\lt$ und $\gt$. Die Zustandsübergangsfunktion ist also

\begin{array}{r} δ : Q \times (Σ \cup {<, >}) \to Q \times {L, R} . \end{array}

Wenn z.B. $\delta(q, x) = (r, L)$ ist, dann heißt das: wenn Du im Zustand $q$ bist und der Lesekopf ein $x$ liest, dann wechsle in den Zustand $r$ und gehe nach links.

Der Automat hat genau einen akzeptierenden und einen ablehnenden Zustand. Wenn ein solcher Zustand erreicht wird, hält der Automat an und gibt 1 bzw. 0 aus. Die von so einem Automaten $M$ akzeptierte Sprache $L(M)$ ist dann definiert als die Menge aller Wörter $\alpha$, die $M$ in einen akzeptierenden Zustand bringen. Beachten Sie, dass $M$ möglicherweise in eine Endlosschleife geraten kann. In diesem Falle ist $\alpha$ kein Wort in $L(M)$.

Zeigen Sie, dass $L(M)$ eine reguläre Sprache ist. Dass man also aus $M$ einen neuen Automaten $M'$ bauen kann, der nur nach rechts laufen kann.

Übungsaufgabe 5.7.4 Sei $\Sigma = \{1,2, \dots, k\}$ und $L$ die Sprache aller Wörter, in denen mindestens ein Zeichen fehlt, also

\begin{array}{r} L = ⋃_{i = 1}^{k} (Σ ∖ {i})^{*} \end{array}

Zeigen Sie, dass ein endlicher Automat für $L$ mindestens $2^k$ Zustände braucht.

Übungsaufgabe 5.7.5 Schreiben Sie eine reguläre Grammatik für $L$ mit höchstens $k+1$ Nichtterminalen.

Übungsaufgabe 5.7.6 (Challange.) Sei $L$ die Sprache aus der vorherigen Aufgabe und $\bar{L} = \Sigma^* \setminus L$ ihr Komplement. $\bar{L}$ ist also die Sprache aller Wörter, in denen jedes Zeichen aus $\Sigma$ mindestens einmal vorkommt.

Zeigen Sie, dass jede reguläre Grammatik für $\bar{L}$ mindestens $2^k$ Nichtterminale benötigt.