Moin,
habe ich hier eine Klasuraufgaben, aber leider habe ich nicht verstanden. Könnte jemand mir erklären . Es wäre schön, wenn es eine kurze Lösung für diese Aufgabe gibt.
Danke sehr.

[IMG]http://farm3.anhso.net/upload/20101004/06/o/anhso-063528_Bildschirmfoto_2010-10-04_um_01.35.06.jpg[/IMG]

[IMG]http://farm3.anhso.net/upload/20101004/06/o/anhso-063544_Bildschirmfoto_2010-10-04_um_01.35.23.jpg[/IMG]

Moin,

deine Frage ist etwas(?) unspezifisch.  Was genau hast du nicht verstanden?

Die Aufgabe behandelt die elementarsten Grundlagen von formalen Sprachen (Wortmengen).  Es geht darum, eine Wortmenge zu begreifen, formal zu beschreiben und durch das einfachste der behandelten Automatenmodelle akzeptieren zu lassen.  Wenn du bei dieser Aufgabe "alles" nicht verstanden hast, fehlt dir die Grundlage für den gesamten Stoff der zweiten Semesterhälfte…

Trotzdem hier der Versuch einer Schritt-für-Schritt-Lösung für die Sprache L1:

Die Menge aller Wörter aus a-s und b-s, die mit a beginnen und mindestens ein b enthalten, lässt sich durch Konkatenation folgender Wortteile bestimmen:
  1. ein a
  2. irgendetwas aus beliebig vielen a-s und b-s
  3. ein b
  4. irgendetwas aus beliebig vielen a-s und b-s
Die regulären Ausdrücke dazu lauten 1. a, 2. (a+b)*, 3. b, 4. wie 2.
Zusammengesetzt mittels Konkatenation ergeben die vier Ausdrücke den gesuchten Gesamtausdruck (einfach hintereinanderschreiben).

Dann wird nach einem Wort gefragt, welches nicht in der Sprache ist.  Das Wort soll aber mit a beginnen (es soll aus {a}∙Σ* stammen).  Es muss also ein Wort sein, welchem das b fehlt, sonst existieren ja keine verletzbaren Anforderungen.  Also zum Beispiel das Wort aa.

Der in Aufgabenteil b) gesuchte endliche Automat ergibt sich direkt aus den Punkten 1.-4.: Vom Startzustand kommt man mit a in den zweiten Zustand, in welchem entlang einer Schleife beliebig viele a-s und b-s gelesen werden können.  Vom zweiten Zustand kommt man mit b in den dritten Zustand, an welchem wieder eine a-/b-Schleife hängt.  Nur, wenn der Automat den dritten Zustand erreicht, hat er ein Wort aus der gesuchten Sprache gelesen, daher ist das der Endzustand.  Z1 enthält also drei Zustände, Zend den dritten Zustand und Σ1 die möglichen Buchstaben {a,b}.

Ich hatte bei der Vorbereitung vor der ersten Klausur (die zum Glück gut bestanden wurde) Probleme mit dem Begriff "rationaler Ausdruck" in der Aufgabenstellung. Dieser war mir im Zusammenhang mit formalen Sprachen vorher nie begegnet.
Habe es dann einfach als "regulärer Ausdruck" interpretiert.  
Sicherlich ist das bei dem Fragesteller auch so.  

L1 = a(a+b)*b(a+b)*

q ————> p ————–>  r (a,b)
       a          (a,b)       b

Danke für ihre Hilfe , aber leider habe ich noch nicht verstanden. Ich hätte gern wissen, wie ich unter den Begriff  'rationale Ausdruck ' verstehen kann?
Ich habe unter ihrer Hinweis bearbeitet, aber ich kann L2 noch nicht haben . Wie ich L2 finden kann ?
Bei teil b) muss ich ein vDFA ( vollständige DFA ) A1 mit L(A1) = L1 finden . Ich versuche vDFA zu zeigen aber irgendwie noch nicht korrekt .
Bitte erklär mir noch mal, wie ich diese Aufgabe schaffen kann. Danke sehr.

zu L2
wie sieht die Sprache für folgende Wörter denn aus?
aab
aabab
aababababab
aabababababab
aababababababab

aab kokateniert mit (ab)*
also L= aab(ab)*

L1: a+b[ab]* oder in der anderen Schreibweise: aa*b(a+b)*
L2: wie kommt ihr da auf so komische Ergebnisse? Es sind doch drin:
a
b
aaa
aab
aba
abb
baa
bab
bba
bbb
dasselbe mit 5 Zeichen (2^5 = 32 Wörter), 7 Zeichen (2^7 = 128 Wörter), etc.
Es steht da nicht, dass das Wort mit a anfangen soll oder a und b immer im Wechsel kommen sollen?!

In "üblicher" Schreibweise ist das dann: [ab]([ab]{2})*, in der anderen wohl
(a+b)((a+b)(a+b))*

Wenn man das direkt in einen Automaten übersetzt, hat der drei Zustände; einen kann man aber wegoptimieren.

Automaten siehe Anhang.

Vielen Dank für Ihre Hilfe . Es wäre prima

Hmm, ich habe wohl etwas an meiner ersten Antwort nachzubessern:

Der feine Unterschied zwischen regulären und rationalen Ausdrücken ist mir in der Aufgabenstellung gar nicht aufgefallen.  Es handelt sich dabei tatsächlich um dasselbe (zumindest für die Zwecke von FGI 1).  Im Diplomstudiengang wurden die Ausdrücke noch als "rational" gelehrt, inzwischen heißen sie "regulär".  Da ist wohl eine alte Formulierung in die Aufgabenstellung hineingerutscht.  (In den abstrakteren Tiefen der theoretischen Informatik gibt es zwar einen Unterschied zwischen rational und regulär, der wird aber bei den regulären Sprachen nicht sichtbar.)

Mein vorgeschlagener endlicher Automat passte nicht auf die Aufgabenstellung - ich habe einen NFA beschrieben, obwohl ein vDFA gefordert war.  Die Lösung von Wulf ist da schon besser (deterministisch), aber noch nicht ganz korrekt (nicht vollständig).  Im Startzustand muss auch eine Kante für den Buchstaben b existieren.  Diese Kante muss zu einem Zustand führen, von dem aus der Endzustand nicht mehr erreichbar ist (Wörter mit einem b am Anfang dürfen nicht akzeptiert werden). Damit der Automat vollständig bleibt, muss auch von diesem Zustand wieder eine Kante für a und für b abgehen - am besten als Schleife zu sich selbst.

War wohl zu spät :)
Dann nimmt man halt meinen minimalen Automaten und fügt noch einen Zustand hinzu, zu dem alle fehlenden Kanten führen.
Btw, welche Vorteile haben vollständige Automaten in der Praxis?

Ich hatte bei der Vorbereitung vor der ersten Klausur (die zum Glück gut bestanden wurde) Probleme mit dem Begriff "rationaler Ausdruck" in der Aufgabenstellung. Dieser war mir im Zusammenhang mit formalen Sprachen vorher nie begegnet.
Habe es dann einfach als "regulärer Ausdruck" interpretiert.  
Sicherlich ist das bei dem Fragesteller auch so.

Die richtigere Bezeichnung wäre immer "rationaler Ausdruck" aber es hat sich mit den Jahren so eingebürgert, dass nun immer von regulären Ausdrücken geschrieben wird.
Ratiolnale Mengen und reguläre Mengen sind unterschiedlich definiert und fallen bei Teilmengen des freien Monoids (Sigma^*, Konkatenation) tatsächlich zusammen.
Es gibt aber Monoide, in denen die Familie der regulären Mengen nicht identisch ist mit der Familie der rationalen Mengen!
Daher diese unterschiedlichen Bezeichnungen!
In den früheren Veranstaltungen zur theoretischen Informatik (F2 und später FGI-1) wurde dieser Unterschied stets kurz angedeutet.
Diese Probeklausursaufgabe ist eben schon recht alt….

was ist unterschied zwischen (a+b)* und (ab)*? eine dumme Frage, aber bitte antwort mir

a+b ist `oder' während ab eine Konkatenation ist.
(a+b)* matcht also bbaaaaaabbbbbbba während (ab)* nur abababababab…. matcht.

SOS könnte jemand diese Aufgabe lösen ? viel viel dank

[IMG]http://ca5.upanh.com/14.291.18517412.7jp0/bildschirmfoto20101006um043117.png[/IMG]

ich weiss nur,dass ich die Regel Elimination implikation in erstem Schritt nehme  . Was/wie muss ich weiter arbeiten ???

Ok, jetzt mal stopp. Das bringt so nichts, dass ihr in zwei Threads die Aufgaben
zur Klausurvorbereitung postet und im Prinzip einfach nur fragt "Wie geht das?".

Die Aufgaben sollen dazu dienen, dass ihr euch mit dem Stoff beschäftigt! Wenn
du die Aufgabe nun vor dir hast und so gar nicht weisst, was Skolemisierung be-
deutet, dann nimm dir bitte das Skript und schlag es da nach. Wenn du dann - nach
einigen Stunden Arbeit! - nicht verstehst, wie *ein bestimmter Aspekt* der Skolemi-
sierung funktioniert, dann kannst du ganz gezielt nachfragen und wirst dann bestimmt
auch eine Antwort kriegen.

Wenn ihr Aufgaben mit Musterlösungen braucht, um hier und da mal zu sehen, wie
etwas funktioniert, dann nehmt euch doch die Aufgabenzettel von diesem und ggf.
den vergangenen Jahren. Ferner sind auf dem Zettel mit den Aufgaben zur Prüfungs-
vorbereitung in der umrahmten Box oben zwei Literaturhinweise gegeben. Bei beiden
Büchern findet man viele Aufgaben, von denen zu vielen eine Lösung (im Buch bzw.
im Web) zur Verfügung gestellt wird. Dort könnt ihr dann üben, um dann erneut
zu versuchen die Aufgaben zur Prüfungsvorbereitung zu lösen.

Das soll jetzt nicht pampig von mir klingen, aber wir haben extra keine Musterlösung
bereitgestellt, damit ihr euch mit den Aufgaben beschäftigt und nicht gleich in Ver-
suchung kommt in der Musterlösung nachzuschlagen. (Die im übrigen auch immer nur
einen Weg präsentieren könnte und oft gibt es mehrere etwas zu tun.) Aufgaben mit
Lösungen gibt es ja zu Hauf in Büchern und im Netz. (Auch findet man meist durch-
gerechnete Beispiele in den Büchern, wenn ein Thema gerade behandelt wird.)

Frank :)

Existenzquantoren "raushauen":

1. ExAyEzAuEv(-P(x,y) v -Q(z,v)) v ((P(u,v) v Q(v,z)) [x/a]
2. AyEzAuEv (-P(a,y) v -Q(z,v)) v ((P(u,v) v Q(v,z)) (Ez hängt von Ay ab)
3. AyAuEv (-P(a,y) v -Q(z,v)) v ((P(u,v) v Q(v,f(y))) (Ey hängt von AyAu ab)
4. AyAu (-P(a,y) v -Q(z,g(y,u) v (P(u,g(y,u)) v Q(g(y,u),f(y))

Weiss auch nicht wie man es genauer beschreibt. Kann einer das Ergebnis bestätigen?  

*aufschreibt

Kleiner Hinweis, weil das einfach kaum lesbar ist:
[ latex ] \exists x \forall y \exists z \vee \wedge \neg [ /latex ]
ohne Leerzeichen in den Klammern.
[latex] \exists x \forall y \exists z \vee \wedge \neg [/latex]

Stimmt mein Ergebnis abgesehen von den richtigen Quantoren?

AyAu (-P(a,y) v -Q(z,g(y,u)) v P(u,g(y,u)) v Q(g(y,u),f(y)))

A -> Allquantor E -> Existenzquantor

Einmal ist das z nicht ersetzt worden, sonst ja.

Frank :)

Eine Anmerkung noch: Es ist bei der Skolemisierung nicht nötig, Äquivalenzumformungen
vorzunehmen, die Junktoren betreffen. (Im Beispiel oben ändert sich die Matrix der gegebenen
Formel also, abgesehen von dem Ersetzen einiger Variablen durch Skolemfunktionen/konstanten,
nicht.)

Frank :)

Ja sehe ich grad. Hab ein z übersehen. Danke