Also dass sie an sich wichtig sind will ich hier garnich bestreiten, aber meint ihr dass es ein wichtiges Thema für die Prüfung sein könnte ?
In den Protokollen habe ich dazu garnix gefunden, aber es gibt ja auch nur 6 Stück.
Wie siehts denn bei euch so aus?

Hmm.. war das nicht eher was für F1/F2 ?

also ich hatte am montag prüfung und da kamen in der hinsicht die fragen:

(nachdem geklärt war was Re ist)

- Aus F2 sind ja reguläre Mengen bekannt.
- Was kennen Sie denn an weiteren Sprachklassen dazwischen?

(also vorallem L1 = Cs)

- Wie sind diese Sprachen definiert?

(L1-Grammatik, Besonderheit der Produktionen)

- Wie kann man zeigen, das L1 echt kleiner ist als L0?

(da solls ein Verfahren im Skript geben,
war H. Farwer sehr wichtig)



sonst noch interessante Fragen neben dem Standard,
für die ich kein extra Protokoll schreiben wollte
(zumal H. Farwer mitliest ;) ):

- Gilt eine T-Invariante für alle Markierungen?

nein, nur für die, in denen auch alle Schaltungen
durchgeführt werden können

- Was tut eine TM, wenn sie ein Wort nicht akzeptiert?

hält nicht an

/edit
bin mir ziemlich sicher, dass das so raus kam
(ich sagte, kann doch ruhig auch in einem nichtendzustand
anhalten, das war aber falsch)
kann ich allerdings im skript bisher nicht finden,



- Warum Nachrichtenkomplexität bei verteilten Algorithmen?

meisst dauert Senden von Nachrichten viel länger als
Arbeitsschritte der beteiligten Prozesse/ Prozessoren
-> geeigneteres Maß für Komlexität
(war eventuell keine Frage sondern hab ich nur so gemutmaßt)

- Warum nicht die Zeit/ Übertragungsdauer für die Nachrichten
- als Maß sondern deren Anzahl?

Prozess soll allgemein beschrieben werden,
Zeit wäre auf jeder Hardware anders,

- Finden Greedy-Algorithmen immer die optimale Lösung eines Problems?

Nein


edit

Hmm.. war das nicht eher was für F1/F2 ?

[img]http://www.fb18.de/gfx/8.gif[/img][img]http://www.fb18.de/gfx/2.gif[/img][img]http://www.fb18.de/gfx/8.gif[/img]


edit2

du solltest lieber darüber nachdenken,
ob WF-Netze und Auftragsysteme drankommen,
das sind mal große gebiete..

Hmm.. war das nicht eher was für F1/F2 ?

Chomsky-NORMALFORMEN sind F2, mit Chomsky-Grammatiken kann ich nichts anfangen, also wirds wohl F3/4 sein.

Achjaaa… aber immerhin hatte ich den Namen behalten können [img]http://www.fb18.de/gfx/22.gif[/img]

Eine TM die ein Wort nicht akzeptiert hält nicht notwendigerweise nicht an, das war nur die urspruengliche Definition von A. Turing. Akzeptiert wird heute über die Erfolgsrechnung definiert wenn ich recht informiert bin, anhalten kann eine TM auch so weil die Überführungsfunktion lückenhaft sein darf, sprich der Automat kann aus dem Zustand nicht mehr raus, ist ein wichtiger unterschied, beim einem weist du das das wort nicht akzeptiert wird beim anderen weisst du es nie ob der automat nicht doch irgendwann anhält

mag gerne so sein,
H. Farwer legt dann also meiner erfahrung nach
wert auf die ursprüngliche definition,

im skript hab ich gar keinen hinweis entdeckt,
kann man dort irgendwo ein statement rauslesen?

im skript hab ich gar keinen hinweis entdeckt,
kann man dort irgendwo ein statement rauslesen?

Dürfte sich ergeben aus der Definition der Sprache einer Maschine (war afair in der Art es gibt eine Erfolgsrechnung so dass man von q0w => uqv kommt mit w dem Wort, u, v elemente aus Sigma* und q ein Endzustand). Ergo dürfte ein nicht-akzeptiertes Wort das Gegenteil sein.

Hmm.. war das nicht eher was für F1/F2 ?

Chomsky-NORMALFORMEN sind F2, mit Chomsky-Grammatiken kann ich nichts anfangen, also wirds wohl F3/4 sein.

Chomsky Typ-3 (irgendwie linksseitig oder sowas, auf jeden Fall gleichmächtig mit Reg) und Typ-2 (kontext-freue) Grammatiken kommen in F2 vor [img]http://www.fb18.de/gfx/28.gif[/img]

Chomsky Typ-3 (irgendwie linksseitig oder sowas, auf jeden Fall gleichmächtig mit Reg) und Typ-2 (kontext-freue) Grammatiken kommen in F2 vor [img]http://www.fb18.de/gfx/28.gif[/img]

Aber nicht unter dem Namen [img]http://www.fb18.de/gfx/25.gif[/img].

Typ 3: einseitig eindeutig.

im skript hab ich gar keinen hinweis entdeckt,
kann man dort irgendwo ein statement rauslesen?

Dürfte sich ergeben aus der Definition der Sprache einer Maschine (war afair in der Art es gibt eine Erfolgsrechnung so dass man von q0w => uqv kommt mit w dem Wort, u, v elemente aus Sigma* und q ein Endzustand). Ergo dürfte ein nicht-akzeptiertes Wort das Gegenteil sein.

stimmt, da steht's ja unmissverständlich, ich kann mal wieder nicht lesen [img]http://www.fb18.de/gfx/26.gif[/img]
bei der turingberechenbarkeit ist das leider nicht so eindeutig

/edit viel später:
gar nicht wahr,
die turingmaschine könnte ja nach dieser definition auch
in einem nichtendzustand anhalten..

Chomsky Typ-3 (irgendwie linksseitig oder sowas, auf jeden Fall gleichmächtig mit Reg) und Typ-2 (kontext-freue) Grammatiken kommen in F2 vor [img]http://www.fb18.de/gfx/28.gif[/img]

Aber nicht unter dem Namen [img]http://www.fb18.de/gfx/25.gif[/img].

Typ 3: einseitig eindeutig.

Seite 93, Kapitel 4: Kontextfreie Sprachen und Chomsky-Typ-2-Grammatiken [img]http://www.fb18.de/gfx/24.gif[/img]