Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

11.05.2011, 07:51

InfoBiensche

Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Meine Frage:
Ich kann mir einfach keinen Automaten für diese Sprache vorstellen...
NOT-EQn = {xy | x element aus {0,1}^n, x!=y}
Ich soll zeigen, dass jeder deterministische Automat mindestens 2^n Zustände hat. Und wie würde ein nichtdeterministischer Automat aussehen?

Meine Ideen:
Ich muss mir ja sozusagen "merken" was mein x war, damit ich es mit dem y vergleichen kann, aber wenn ich für jede eingabe einen neuen Zustand aufmache werden das viel zu viele...

11.05.2011, 19:11

Roman Oira-Oira

Auf diesen Beitrag antworten »

RE: Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?
Erstens: Deine Aufgabe ist ziemlich ungenau angegeben!

Meinst du vielleicht eher diese Sprachbeschreibung?

$\begin{eqnarray*} \{xy | x \in \{0, 1\}^n \wedge y \in \{0, 1\}^n \wedge x \neq y \} \end{eqnarray*}$ , wobei $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ gleich lange aber unterschiedliche 0-1-Kombinationen sind und $\begin{eqnarray*} xy \end{eqnarray*}$ die Konkatenation der Wörter $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ ist.

Und von welcher Art Automat sprichst Du überhaupt?

Wenn es sich um eine reguläre Sprache (Typ-3-Sprache) handelt, so würde zur Erkennung ein deterministischer endlicher Automat ausreichen, da nicht-deterministische endliche Automaten dieselbe Sprachklassen erkennen.

Handelt es sich allerdings um eine kontextfreie Sprache (Typ-2-Sprache), so reicht ein endlicher Automat zur Erkennung nicht mehr aus. Hier wäre ein Kellerautomat erforderlich, wobei deterministische und nicht-deterministische Kellerautomaten verschiedene Sprachklassen erkennen.

Ich bin mir allerdings nicht sicher, ob es sich hier um eine Typ-2-Sprache handelt, oder nicht! Allerdings erscheint mir Typ-2 hier naheliegender als Typ-3.

Vielleicht solltest du dich mit derartigen Fragen aber lieber an das Informatik-Board wenden. Dort sitzen die Leute, die zum Thema formale Sprachen die Antworten bestimmt aus dem Ärmel schütteln.

11.05.2011, 20:50

kiste

Auf diesen Beitrag antworten »

Beachte, dass n fest ist. Also ist das merken von x kein Problem im Zustand selbst. Dafür braucht man dann aber natürlich die 2^n Zustände.

12.05.2011, 11:44

Roman Oira-Oira

Auf diesen Beitrag antworten »

Zitat:

Original von kiste
Beachte, dass n fest ist. Also ist das merken von x kein Problem im Zustand selbst. Dafür braucht man dann aber natürlich die 2^n Zustände.

Ich glaube, du hast recht! Das geht aber aus der Aufgabenstellung nur dann hervor, wenn man auf den Namen "NOT-EQn" achtet, wo man natürlich nur ein festes "n" schreiben kann - z.B. "NOT-EQ2"

Ist $\begin{eqnarray*} n \end{eqnarray*}$ fest, dürfte ein deterministischer endlicher Automat ausreichen die Sprache zu erkennen, nicht aber, wenn $\begin{eqnarray*} n \end{eqnarray*}$ nicht fest ist!

Nochmals zur Verdeutlichung:

Für festes $\begin{eqnarray*} n \end{eqnarray*}$ (z.B. $\begin{eqnarray*} n = 2 \end{eqnarray*}$ ) enthielte die Sprache die folgenden Worte: $\begin{eqnarray*} \text{NOT-EQ2} = \{0001 ,0010, 0011, 0100 ,0110 ,0111 ,1000 ,1001 ,1011 ,1100 ,1101 ,1110 \} \end{eqnarray*}$

Eine weitere Möglichkeit wäre aber die Sprache als NOT-EQ2' zu interpretieren, bei der über die Länge des zweiten Teilwortes $\begin{eqnarray*} y \end{eqnarray*}$ nichts ausgesagt wird (so wie in der ursprünglichen Aufgabenstellung):

NOT-EQ2' enthielte dann genau die Worte bestehend aus dem ersten Teilwort $\begin{eqnarray*} x \in \{0, 1\}^2 \end{eqnarray*}$ gefolgt von dem Teilwort $\begin{eqnarray*} y \end{eqnarray*}$ , für das mehrere Möglichkeiten gegeben sind:

a) $\begin{eqnarray*} y = \varepsilon \end{eqnarray*}$ (das leere Wort)

b) $\begin{eqnarray*} y \in \{0, 1\}^2, y \neq x \end{eqnarray*}$

c) $\begin{eqnarray*} y \in \{0, 1\}^m, m > 2 \end{eqnarray*}$

edit: eine Möglichkeit habe ich vergessen:

d) $\begin{eqnarray*} y = 0 \vee y = 1 \end{eqnarray*}$

Der Aufgabensteller sollte sich zunächst mal dazu äußern, wie die Sprache denn nun genau definiert ist!

Zu Überlegungen bezgl. des endlichen Automaten möchte ich mich noch zurückhalten.

Aber es ist zumindest sehr einfach zu zeigen, daß der endliche Automat mindestens $\begin{eqnarray*} 2^n \end{eqnarray*}$ Zustände braucht, um die Sprache zu erkennen (kiste hat ja sozusagen bereits die Antwort geliefert). Diese Anzahl wird aber auf keinen Fall ausreichend sein.

-----

Ich bin erst heute Abend wieder hier!

Neue Frage »

Antworten »

Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Verwandte Themen