DEAS zu diesen drei Sprachen

Question

Frage:

\( L_{1}:=\left\{w \in\{a, b\}^{*} \mid\right. \) in \( w \) kommt das Infix \( a b b \) nicht vor \( \} \)


\( L_{2}:=\left\{\left.w \in\{a, b, c\}^{*}|| w\right|_{a}+|w|_{b}\right. \) ist durch 3 teilbar \( \} \)

\( L_{3}:=\left\{w \in\{a, b, c\}^{*} \mid\right. \) wenn \( a c \) als Infix in \( w \) vorkommt, dann auch \( \left.c a\right\} \)

Könnte mir jemand einen Tipp geben wie ich DEAs zu diesen Sprachen konstruieren könnte?

Code:

Answer 1

\(L_1\): Ein Zustand "\(a\) wurde gelesen", ein Zustand "\(ab\) wurde gelesen", ein Zustand "\(abb\) wurde gelesen".

\(L_2\): Konstruiere einen Automat für

        \(\left\{w \in\{a, b, c\}^{*}|\ |w| \text{ ist durch 3 teilbar}\right\} \)

und passe dann die Zustandsübergänge an.

\(L_3\): Ein Zustand "\(ac\) wurde gelesen", ein Zustand "\(ca\) wurde gelesen", ein Zustand "\(ac\) und \(ca\) wurde gelesen".

Comments

Ist das ein richtiger Automat für die erste Sprache?

---

Das ist schon mal ein guter Anfang. Aber

• Der Automat akzeptiert \(babb\), soll er aber nicht.
  
• Der Automat akzeptiert \(ab\) nicht, soll er aber.
  

Den Zustand \(q_4\) benötigst du nicht. Stattdessen

        \(\begin{aligned}q_0&\stackrel{b}{\to}q_0\\q_2&\stackrel{a}{\to}q_1\end{aligned}\)

und Endzustände sind \(q_0\), \(q_1\) und \(q_2\).

---

Aber wenn q3 kein Endzustand ist, dann wird ein Wort wie aaa...aabb nicht akzeptiert, obwohl es akzeptiert werden sollte - oder?

---

Das Wort \(u\in \Sigma^*\) ist Infix des Wortes \(w\in \Sigma^*\) , wenn es \(p,s\in \Sigma^*\) gibt, so dass

        \(w = p\circ u\circ s\)

ist.

Wegen \(\varepsilon \in \Sigma^*\) ist jedes Präfix und jedes Suffix auch ein Infix. Deshalb sollte \(aaa\dots aabb\) nicht akzeptiert werden.

---

Das ist mein Automat zur dritten Sprache stimmt er ?

---

bzw. könntest du mir dann den korrekten Automaten zeigen.

---

Der Automat akzeptiert das Wort \(cac\) nicht.