Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Nfa

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Nfa

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Nfa

Zitatantwort auf diesen Beitrag erstellen

Hallo,
sitze hier schon bei Teilaufgabe a) fest
"Zeichnen" ist mir klar wie der NFA auszusehen hat.

Nun die Akzeptierte Sprache:

L(M)={w element Summe^ | Delta^(S,w) Schnittmenge leere Menge}

Hier muß ich doch nun w ersetzen , weiß aber nicht mit was.
(Mich irritiert wahrscheinlich auch da man nicht weiß was Anfangs oder auch Endzustand ist)

Pampelmuse hat dieses Bild (verkleinerte Version) angehängt:

20.04.2007 18:08

Nehmen Sie Pampelmuse in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Anfangs- und Endzustände sind im allerersten Satz definiert: Ein NFA M = (...)
Guck dir das Tupel an und schau in deine Definition an welcher Stelle die Anfangs- und Endzustände beschrieben werden.

20.04.2007 19:23

Nehmen Sie Tobias in Ihre Freundesliste auf

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Ahh,
sehs jetzt sofort :
z_0,z_1 element S
z_2 element F

Sum^ist doch die Menge aller Wörter über Sum wobei Sum das endliche und nicht leere Alphabet ist.

=> w:={
wird mir immer noch nicht klar .
reicht einfach Delta({z_0,z_1},w) wobei ein endzustand z_2 exestiert ?

Oder kann ich einfach screiben :
Die akzeptierte Sprache von M des NFA ist {a}^{b}^

Dieser Beitrag wurde 6 mal editiert, zum letzten Mal von Pampelmuse: 22.04.2007 11:07.

21.04.2007 09:58

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Also wenn ich es jetzt richtig eingeschätzt habe, dann beschreibt der Automat eine Sprache, die durch einen solchen Regulären Ausdruck ausgedrückt werden kann:

$[latex]ab^\ast \; \vee \; a^+b^+ \; \vee \; a^\ast b^+ [/latex]$

22.04.2007 11:21

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Habe natürlich versucht dies nur in einer Möglichkeit zu schreiben. ist aber anscheinend nicht möglich.
a^* bedeutet doch soviele a wie man will oder gar nichts.

was bedeutet den a^+ ?

22.04.2007 11:31

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ja, a* bedeutet beliebig viele a's (inklusive der Möglichkeit kein a)

a^+ kann man dann ausdrücken als aa*. Also beliebig viele a's aber mindestens eins.

Und genau das ist hier der Knackpunkt weshalb es schwierig ist die drei Ausdrücke zusammenzufassen. Aber man kann ja auch eine Sprache als Vereinigung von drei Mengen angeben. Versuch es doch mal.

22.04.2007 11:48

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Ich denke mal :

ab^* Vereinigung a^+b^+ Vereinigung a^*b^+ element L(M)

22.04.2007 12:05

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Das ist keine Definition einer Menge. Eine Mengendefinition für a^*b^+ wäre z.B.

$[latex]L = \big\{ vw \; | \; v \in \{a\}^\ast, \; w \in \{b\}^+ \big\}[/latex]$

22.04.2007 13:07

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Ah,ok:

$[latex]L(M) = \big\{ w \; | \; w \in \{(ab^*),(a^+b^+),(a^*b^+\} \big\}[/latex]$

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Pampelmuse: 22.04.2007 14:42.

22.04.2007 13:22

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Also bei dir ist w ein Element aus einer Menge von regulären Ausdrücken? Also ist w ein regulärer Ausdruck?

Du schmeißt da ein bisschen was durcheinander.

22.04.2007 16:43

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

w ist doch element Sum^* die Menge aller Wörter über Sum wobei Sum das endliche und nicht leere Alphabet ist.

Aber weiß nicht welche Sprache M akzeptiert.
Versuchs mal:

L(M)= {vw Vereinigung v_1w_1 Vereinigung v_2w_2| v element {a}, w element {b}^* , v_1 element {a}^+, w_1 element {b}^+, v_2 element {a}^*, w_2 element {b}^+}

22.04.2007 19:31

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Das kommt der Sache schon näher. Aber warum vereinigst du innerhalb der Mengen? Man vereinigt doch Mengen.

22.04.2007 22:04

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Also so?
L(M)= {uv Vereinigung wx Vereinigung yz| u element {a}, v element {b}^* ,w element {a}^+, x element {b}^+, y element {a}^*, z element {b}^+}

23.04.2007 07:27

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Hätte nicht gedacht, dass du so zäh bist. großes Grinsen

$[latex]L(M) = \big\{ ... \big\} \cup \big\{ ... \big\} \cup \big\{ ... \big\}[/latex]$
So vereinigt man drei Mengen. Eine Vereinigungsoperation innerhalb einer Menge wie bei dir $[latex]L(M) = \big\{ uv \cup wx \cup yz \big\}[/latex]$ ist falsch, denn so bezieht sich ja die Vereinigung auf Wörter und nicht auf Mengen. Auf Wörtern ist aber keine Vereinigung definiert.

23.04.2007 10:07

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

lol irgendwann wird man auch schlauer.
Also wie mein vorheriger Beitrag nur einzeln.
Besten Dank Tobias

23.04.2007 12:39

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Nfa