ForSA HA2 A5

Abgabe

$$\begin{array}{rl}[\epsilon {]}_{\equiv A}& =\{\epsilon \}\\ [0{]}_{{\equiv }_A}& =\{x0\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=1\}\\ [01{]}_{{\equiv }_A}& =\{x1\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=1\}\\ [00{]}_{{\equiv }_A}& =\{x0\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=0\}\\ [1{]}_{{\equiv }_A}& =\{x1\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=0\}\\ [11{]}_{{\equiv }_A}& =\{x11y\mid x,y\in {\Sigma }^{\ast }\}\end{array}$$

$M_A=\{[\epsilon ],[0],[01],[00],[1],[11]\},\Sigma ,{\delta }_A,[\epsilon ],\{[\epsilon ],[0],[01]\}$, wobei ${\delta }_A$ durch den folgenden Graphen gegeben ist:

\begin{figure}[hp]
    \centering
\tikzstyle{alter}=[circle, minimum size=16pt, draw, inner sep=1pt] 
\tikzstyle{majarr}=[draw=black]
\begin{tikzpicture}[auto, >=stealth']
    \tikzstyle{majarr}=[draw=black,->,shorten <=1.5pt, shorten >=1.5pt]
    \node[alter, initial, accepting, initial text=] at (0,0) (e) {$[\varepsilon]$};
    \node[alter, accepting] at (2,0) (0) {$[0]$};
    \node[alter] at (0,-2) (1) {$[1]$};
    \node[alter, accepting] at (4,0) (01) {$[01]$};
    \node[alter] at (2,-2) (00) {$[00]$};
    \node[alter] at (4,-2) (11) {$[11]$};
 
    \draw[majarr] (e) edge node[midway, anchor=south] {$\scriptstyle 0$} (0);
    \draw[majarr] (e) edge node[midway, anchor=east] {$\scriptstyle 1$} (1);
    \draw[majarr] (0) edge[bend left=10] node[midway, anchor=west] {$\scriptstyle 0$} (00);
    \draw[majarr] (0) edge node[midway, anchor=south] {$\scriptstyle 1$} (01);
    \draw[majarr] (01) edge node[midway, anchor=west] {$\scriptstyle 0$} (00);
    \draw[majarr] (01) edge node[midway, anchor=west] {$\scriptstyle 1$} (11);
    \draw[majarr] (00) edge[bend left=10] node[midway, anchor=east] {$\scriptstyle 0$} (0);
    \draw[majarr] (00) edge node[midway, anchor=south] {$\scriptstyle 1$} (1);
    \draw[majarr] (1) edge node[midway, anchor=east] {$\scriptstyle 0$} (0);
    \draw[majarr] (1) edge[bend right=43] node[midway, anchor=south] {$\scriptstyle 1$} (11);
    \draw[majarr] (11) edge[loop right] node {$\scriptstyle 0,1$} (11);
\end{tikzpicture}
\end{figure}

Aufgabenstellung

Sei ${\mathbb{N}}_{\ge 2}=\{n\in \mathbb{N}\mid n\ge 2\}$. Gegeben seien das Alphabet $\Sigma =\{0,1\}$ und die Sprache

\begin{multline*} A = \Big\{ w \in \Sigma^{*} \mid \Big( \big( \forall\, n \in \mathbb{N}_{ \ge 2} \,.\, \big( n \le \left| w \right| \land (w)_{n} = 1 \big) \to (w)_{n - 1} = 0 \big) \\ \land \left| w \right|_{0} \bmod 2 = 1 \Big) \lor \left| w \right| = 0 \Big\} \end{multline*}

Eigenschaften der Sprache in natürlichem Deutsch

Ein Wort $w$ gehört zu $A$, wenn entweder

• es das Wort leer $\epsilon$ ist, oder
• jede $\text{Eins in w von einer Null vorangegangen}$ wird und die Anzahl der Nullen ungerade ist.

Beispiele für Wörter

$$\epsilon ,01,0001,0010,00101,0100100$$

Darstellung als Automat

$$\begin{array}{rl}[\epsilon {]}_{\equiv A}& =\{\epsilon \}\\ [0{]}_{\equiv A}& =\{x0\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=1\}\\ [01{]}_{\equiv A}& =\{x1\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=1\}\\ [00{]}_{\equiv A}& =\{x0\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=0\}\\ [1{]}_{\equiv A}& =\{x1\mid x\in {\Sigma }^{\ast }\wedge {\left|x\right|}_0\mathrm{mod}2=0\}\\ [11{]}_{\equiv A}& =\{x11y\mid x,y\in {\Sigma }^{\ast }\}\end{array}$$

$M_A=\{[\epsilon ],[0],[01],[00],[1],[11]\},\Sigma ,{\delta }_A,[\epsilon ],\{[\epsilon ]\}$, wobei ${\delta }_A$ durch den folgenden Graphen gegeben ist:

Äquivalenzklassen

$$\text{Weg zum Zustand}\text{Rundweg vom Zustand}$$

Das Wort ist leer. Es gibt nur ein leeres Wort und der $\epsilon$-Zustand kann nicht anders erreicht werden:

$$[\epsilon {]}_{{\equiv }_A}=\{\epsilon \}$$

Die letzte Ziffer ist $0$ und ${\left|w\right|}_0$ ist ungerade. Wir kommen nur direkt über $0$ dort hin:

$$[0{]}_{{\equiv }_A}=L(0(00+010+100{)}^{\ast })$$

Die letzte Ziffer ist $0$ und ${\left|w\right|}_0$ ist gerade:

$$[00{]}_{{\equiv }_A}=L(0(0+10)(00+010+100{)}^{\ast })$$

Die letzte Ziffer ist $1$ und ${\left|w\right|}_0$ ist ungerade:

$$[01{]}_{{\equiv }_A}=L(0(00{)}^{\ast }1(0(00+100{)}^{\ast }01{)}^{\ast })$$

Die letzte Ziffer ist $1$ und ${\left|w\right|}_0$ ist gerade:

$$[001{]}_{{\equiv }_A}=L(0(0+10)(00+010{)}^{\ast }1(0(00+100{)}^{\ast }01{)}^{\ast })$$

Es gibt eine Eins ohne Null als Vorgänger. Wir müssen zum $\epsilon$-Zustand, oder zu einem Eins-zuletzt-Zustand und ggf. dort kreisen. Mit einer $1$ kommen wir in diesen Zustand. Dort bleiben wir ewig:

\begin{multline*} [ 1 ]_{ \equiv_{A} } = \operatorname{L} \Bigg( \textcolor{magenta}{\bigg( \varepsilon + \Big( 0 (00)^{*} 1 \big( 0(00 + 100)^{*} 01 \big)^{*} \Big) +} \\ \textcolor{magenta}{\Big( 0 (0 + 10) (00 + 010)^{*} 1 \big( 0(00 + 100)^{*} 01 \big)^{*} \Big) \bigg) 1} \textcolor{limegreen}{(0 + 1)^{*}} \Bigg) \end{multline*}

ForSA HA2 Aufgabe5 Notizen

---

Sources:

Related:

Tags: ForSA HA2 zum 2023-07-13