You are not logged in.

Search results

Search results 1-5 of 5.

Monday, April 21st 2008, 2:26pm

Author: broetchen

Frage zum Skript Formale Sprachen

Ich hätte da eine Frage zum Satz von Immermann und Szelepczényi von S.50 im Skript von Vollmer: Im Algorithmus zum Beweis steht folgendes: Source code 1 2 3 4 5 6 7 For all K mit Platz s do begin rate nichtdeterministisch (a) oder (b) (a) falls sich K in t Schritten aus K_start ableiten läßt m=m+1; (b) mache nichts; end if m!=n then ablehnen... Es werden also genau die n Konfigurationen geraten, die sich in t Berechnungsschritten ergeben können. Wo liegt denn das Problem wenn ich das determinist...

Friday, April 18th 2008, 7:06pm

Author: broetchen

Formale Sprachen: Frage zur Prüfung?

Ach ja und: Gibt es eigentlich noch jemanden, der bald Prüfung bei Vollmer hat? Würde mich gerne mal austauschen mit jemandem. Dabei lernt man ja oft auch nochmal einiges. Und da ich mich - wie gesagt - als Nicht-Informatiker eingeschlichen habe, kenne ich einfach niemanden der auch grade dabei ist. Wäre super!

Friday, April 18th 2008, 6:41pm

Author: broetchen

Formale Sprachen: Frage zur Prüfung?

Stimmt... das ist einleuchtend. Vielen Dank! Das ist im Prinzip auch das was ich überlegt hatte, wobei das genaue aufschreiben nicht so leicht ist, wie es auf den ersten Blick aussieht. Man weiß ja zunächst noch nicht welcher Knoten im Graph zu M mit welchem Knoten im Graph von M' korespondiert. Deswegen hatte ich noch eine Liste T[z'] mit benutzt und dort T[z'] = z gesetzt falls sich beim verfolgen der Kanten herausstellt, dass z' mit z korrespondiert - der Isomorphismus also f(z) = z' leisten ...

Friday, April 18th 2008, 4:17pm

Author: broetchen

Formale Sprachen: Frage zur Prüfung?

Hab auch mal ne Frage: Man zeigt die Äquivalenz zweier regulärer sprachen ja indem man zeigt, indem man zunächst aus den Automaten die sie entscheiden die zugehörigen minimalen Automaten konstruiert (siehe Algorithmus im Skript). Dann überprüft man ob die so gewonnenen Minimalautomaten isomorph zueinander sind. In einem Protokoll stand nun, dass Vollmer nach einem Polynomialzeit-Algorithmus gefragt hat um die Isomorphie zweier Automaten zu zeigen. Leider steht so ein Algorithmus nicht im Skript....