0 Daumen
97 Aufrufe

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:

von

1 Antwort

0 Daumen
 
Beste Antwort

\(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".

von 4,0 k

dfaLA1.png

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.

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr.png

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community