Generellen NEA bauen mit einer 1 an der n-ten letzen Position

05.03.2014, 13:05	un1x	Auf diesen Beitrag antworten »
Generellen NEA bauen mit einer 1 an der n-ten letzen Position Hi Ich habe eine Aufgabe wo ich einen Nichtdeterministischen Endlichen Automaten definieren soll, so dass die akzeptierende Sprache $\begin{eqnarray} L(M_n) = \left\{ w \in \{0,1\}^ \big \| x1y \textit{ für } x \in \{0,1\}^* \textit{ und } y \in \{0,1\}^{n-1}\right\} \end{eqnarray}$ akzeptiert wird. (An der n-ten letzen Stelle eine 1) Wenn ich mir z.b $\begin{eqnarray} n=4 \end{eqnarray}$ anschaue, dann könnte der Automat wiefolgt aussehen [attach]33452[/attach] Und würde das Wort 101001 zulassen. Ich habe grundsätzlich schon eine Idee wie ich es machen muss, habe aber Probleme dies korrekt zu definieren. Es gibt 1+n Zustände Der n-te Zustand ist der akzeptierende Ich bleibe solange auf dem Startzustand, bis ich nur noch n-stellen zu verarbeiten habe Wenn an der n-ten letzen Stelle eine 1 kommt Können n-1 mal 0 oder 1 folgen Mein Ansatz sieht sehr kompliziert aus.. Vielleicht gibts bessere Methoden um dies zu definieren $\begin{eqnarray} <br /> M_n = (Q_n, \{0,1\},\delta _n,q_0,F), n \in \mathbb{N}\\<br /> Q_n = \{q_0,...,q_{n-1},q_n\}, \|Q_n\|=n+1\\<br /> F=\{q_{n}\}\\\\<br /> \delta _n(q,a) = \begin{cases}<br /> \{q_0\} & q=q_0 \land a \in \{0,1\}\\<br /> \{q_1\} & q=q_0 \land a = 1\\<br /> \{q_k\} & q=q_{k-1} \land a \in \{0,1\} \textit{ bei } q_k \in Q_n\\<br /> \end{cases}<br /> \end{eqnarray*}$
06.03.2014, 23:00	chrizke	Auf diesen Beitrag antworten »
RE: Generellen NEA bauen mit einer 1 an der n-ten letzen Position Dein Ansatz ist meiner Meinung nach fast richtig und alles andere als kompliziert. Lediglich bei den Transitionen in der letzten Zeile solltest du formal etwas genauer sein. Da schreibst du $\begin{eqnarray} <br /> \{q_k\} \quad q=q_{k-1} \land a \in \{0,1\} \textit{ bei } q_k \in Q_n.<br /> \end{eqnarray}$ Dieses $\begin{eqnarray} q_k \end{eqnarray}$ darf aber nicht jedes aus $\begin{eqnarray} Q_n \end{eqnarray}$ sein, denn $\begin{eqnarray} Q_n \end{eqnarray}$ ist die Menge aller Zustände und enthält auch den Startzustand $\begin{eqnarray} q_0 \end{eqnarray}$ und für den soll diese Regel ja eben nicht gelten. Du solltest stattdessen eher sowas schreiben wie $\begin{eqnarray} <br /> \{q_k\} \quad q=q_{k-1} \land a \in \{0,1\} \textit{ mit } k>1.<br /> \end{eqnarray}$ Je nachdem wie ihr Transitionen definiert habt, musst du da nochmal aufpassen. Momentan sieht es so aus, als sei $\begin{eqnarray} \delta_n:Q\times\Sigma\to\mathbb{P}(Q) \end{eqnarray}$ . Normalerweise hat man ja eher sowas wie $\begin{eqnarray} q\stackrel{a}{\to}p \end{eqnarray}$ , also eine Abbildung auf ein einzelnes Element und keine Menge, so wie es die geschwungenen Klammern bei dir suggerieren.
06.03.2014, 23:36	un1x	Auf diesen Beitrag antworten »
Danke vielmals für deine Antwort. Das ist richtig. Unsere Definition für NEA ist mit der Funktion zu einer Potenzmenge. Wäre anders für eine DEA. Muss ich eigentlich noch den letzten Zustand auch definieren? Also von $\begin{eqnarray} \delta(q_{n},a) = \emptyset \end{eqnarray}$ Zudem muss ich bei deinem Lösungsansatz auch definieren, kass $\begin{eqnarray} k <= n \end{eqnarray}$ sein muss oder?
07.03.2014, 09:29	un1x	Auf diesen Beitrag antworten »
Habe die Transitionen so definiert: $\begin{eqnarray} \delta_n(q,a)=\begin{cases}<br /> \{q_0\} & q=q_0 \land a \in \textstyle\sum^\\<br /> \{q_1\} & q=q_0 \land a=1\\<br /> \{q_k\} & q=q_{k-1} \land a \in \textstyle\sum, 1 < k \leq n\\<br /> \emptyset & q=q_n \land a \in \textstyle\sum\nolimits^<br /> \end{cases} \end{eqnarray}$
07.03.2014, 20:50	chrizke	Auf diesen Beitrag antworten »
Hier musst du nun auch wieder mit den Details aufpassen. Das $\begin{eqnarray} a \end{eqnarray}$ in den Transitionen ist ja immer nur ein Buchstabe und kann somit nur Element von $\begin{eqnarray} \Sigma \end{eqnarray}$ sein, nicht aber von $\begin{eqnarray} \Sigma^. \end{eqnarray}$ Dann würde ich, wenn man sich im letzten Zustand befindet und doch noch irgendwelche Buchstaben lesen will nicht in die leere Menge zeigen, sondern wieder nach $\begin{eqnarray} q_0 \end{eqnarray}$ . Das ist in diesem Fall hier auch möglich. Als letztes würde ich, wenn ihr schon auf Mengen abbildet, diese auch nutzen – besonders für den nichtdeterministischen Übergang von $\begin{eqnarray} q_0 \end{eqnarray}$ aus. Dann ist es auch deutlicher, dass es sich hier um einen NEA handelt. Ich würde sowas vorschlagen: $\begin{eqnarray} \delta_n(q,a) = \begin{cases} \{q_0\} & q=q_0\land a = 0\\ \{q_0,q_1\} & q=q_0 \land a=1\\ \{q_{k+1}\} & q=q_{k} \land a\in\Sigma,\ 1 \leq k < n \\ \{q_0\} & q=q_n \land a\in\Sigma\end{cases} \end{eqnarray*}$
10.03.2014, 11:13	un1x	Auf diesen Beitrag antworten »
Danke für den Tipp. Jedoch $\begin{eqnarray} a \end{eqnarray}$ könnte ja auch das leere Wort $\begin{eqnarray} w \end{eqnarray}$ sein und das ist in $\begin{eqnarray} \Sigma \end{eqnarray}$ nicht definiert?
Anzeige

10.03.2014, 18:00	chrizke	Auf diesen Beitrag antworten »
Es ist zwar richtig, dass es bei NEAs auch einen s.g. Epsilon-Übergang (Zustandswechsel ohne einen Buchstaben zu lesen) geben kann, ich sehe bei diesem Automaten hier aber keine Notwendigkeit, davon auch Gebrauch zu machen. Zudem ist ja $\begin{eqnarray} \Sigma^ \end{eqnarray}$ (Kleenesche Hülle) definiert als alle endlichen Wörter über dem Alphabet $\begin{eqnarray} \Sigma \end{eqnarray*}$ sowie das leere Wort. Somit ist dies nicht zu gebrauchen, wenn du ausdrücken willst: "Ein Element des Alphabets oder das leere Wort", da ja auch alle anderen Wörter über dem Alphabet in der Kleeneschen Hülle enthalten sind.
10.03.2014, 20:36	un1x	Auf diesen Beitrag antworten »
das stimmt. Danke dir.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »