Aufgabe:
Sei $$ \varphi_{1}(L)=\left\{w \in \Sigma^{*} | \text { es gibt ein } \alpha \in \Sigma^{*} \text { mit }|\alpha|=|w| \text { und } \alpha w \in L\right\} $$
$$ \begin{array}{l}{\text { Beweis. Wir wollen zeigen, dass } \varphi_{1}(L) \text { für alle Sprachen } L \in \operatorname{REG} \text { regulär ist. Sei dazu } L \in \operatorname{REG} \text { beliebig. Da } L \text { regulär ist, }} \\ {\text { gibt es einen DFA } M \text { mit L}(M)=L \text { Wir konstruieren nun aus } M \text { einen } \lambda^{\prime} \operatorname{mit}\left(M^{\prime}\right)=\varphi_{1}(L) . \text { Dazu beschreiben wir }} \\ {\text { die Arbeitsweise von } M^{\prime} \text { zunächst informell die Zustandsmenge von } M^{\prime} \text { ist (konzeptionell) jene von } M . \text { Die Berechnung }} \\ {\text { von } M^{\prime} \text { funktioniert (konzeptionell) wie folgt: anstelle eines Steins der zu Beginn der Berechnung auf } q_{0} \text { gelegt wird, }}\end{array} $$ $$ \begin{array}{l}{\text { platzieren wir drei Steine (einen weißen, einen roten und einen blauen) auf die Zustände von } M . \text { Den blauen Stein legen }} \\ {\text { wir auf } q_{0} \text { , den roten und weißen auf einen nichtdeterministisch geratenen Zustand } q_{i} \text { (beide Steine auf den selben Zustand). }} \\ {\text { Die Berechnung von } M^{\prime} \text { auf Eingabe } w \in \Sigma^{*} \text { funktioniert nun (konzeptionell) wie folgt: <Beschreiben Sie hier, wie die }} \\ {\text { drei Steine pro gelesenem Symbol verschoben werden (sie können auch auf einem Zustand liegen bleiben). Definieren Sie }} \\ {\text { außerdem, wann } M` \text { ein Wort akzeptiert. }}\end{array} $$ $$ \text { Abschließend zeigen wir noch, wie ein tatsächlicher } \lambda \text { -NFA die oben beschriebene Arbeitsweise umsetzen kann, indem } $$ $$ \text { wir explizit seine Zustandsmenge und Übergangsrelation angeben: } $$
Problem/Ansatz:
Kann mir das bitte jemand erklären? Wie man da vorgehen muss?
