Formale Sprachen: Frage zur Prüfung?

Trainee

Date of registration: Nov 5th 2006

Thursday, March 27th 2008, 8:20pm

in der Prüfung wurde es gefragt (Beispielweise) ob das Leerheitsproblem für CFL entscheidbar oder nicht? sollte man bei solch Fragen den Beweis können oder antwortet man nur mit ja oder nein.

Grüße,

Bishara

Go to the top of the page

oixio

Senior Schreiberling

Posts: 517

Date of registration: Oct 3rd 2004

2

Thursday, March 27th 2008, 8:52pm

Ich wurde teilweise auch nach der Beweisidee gefragt. Bis ins kleinste Detail wirst du es aber wohl nicht können müssen.

Dieser Post wurde aus 100 % chlorfrei gebleichten, handelsüblichen, freilaufenden, glücklichen Elektronen erzeugt!

Go to the top of the page

Bishara

Trainee

Posts: 33

Date of registration: Nov 5th 2006

3

Thursday, March 27th 2008, 8:56pm

Danke

Bishara

Go to the top of the page

Bishara

Trainee

Posts: 33

Date of registration: Nov 5th 2006

4

Saturday, March 29th 2008, 10:37pm

hallo,

ich habe noch eine Sache die mir immer noch nicht ganz klar gewesen und zwar einer deterministischer Kellerautomat akzeptiert sein Eingabe wenn er die Eingabe bis Ende liest und dann in einem Endzustand landet und der Keller spielt keine Rolle in diesem Fall.

aber die Sprachen die von deterministischen Kellerautomaten mit leerem Keller akzeptiert sind deterministisch kontextfrei Sprachen mit Präfixeigenschaft die sog. LR(0)-Sprachen (Seite 36). davon könnte man ausgehen und sagen, dass die deterministische kontextfreie Sprachen mit Präfixeigenschaft sind eine Teilmenge von die deterministische kontextfreie Sprachen.

sollte es alles richtig sein ?

Bishara

Go to the top of the page

ctk

Trainee

Posts: 113

Date of registration: Oct 15th 2004

5

Friday, April 4th 2008, 5:53pm

Ich hoffe es nützt dir noch was: Ja genau, LR(0) ist eine echte Teilmenge der deterministischen kontextfreien Sprachen welche auch LR(k)-Sprachen genannt werden. Über die erfährt man übrigens alles wissenswerte (und darüber hinaus

in Compiler-Konstruktion I

Technik ist der Wettlauf der Intelligenz mit der Kreativität der Narren.
Bis heute haben die Narren immer gewonnen.

Go to the top of the page

broetchen

Praktikant

Posts: 5

Date of registration: Apr 18th 2008

6

Friday, April 18th 2008, 4:17pm

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. Ich hab mir zwar einen überlegen können, aber er kommt mir ungeschickt vor. Wie würdet ihr das machen?

Zu überprüfen ist doch eigentlich ob

1) |Z| = |Z'|

2) für alle x,y mit z_0 x = z_0 y gdw. z_0' x = z_0' y (injektivität)

Oder???

Go to the top of the page

thz.

Praktikant

Posts: 31

Date of registration: Oct 5th 2007

7

Friday, April 18th 2008, 6:05pm

Quoted from "broetchen"

Hab auch mal ne Frage:

Zu überprüfen ist doch eigentlich ob

1) |Z| = |Z'|

2) für alle x,y mit z_0 x = z_0 y gdw. z_0' x = z_0' y (injektivität)

Oder???

Das würde aufgrund der Minimalität reichen. Allerdings kannst du nicht in Polyzeit für alle Wörter x, y aus \Sigma* prüfen. Deswegen prüft man lieber direkt die Isomorphie der beiden Automaten, also der Graphen mit Beschriftung. Man führt einfach auf dem einen Automaten eine Suche durch, und guckt ob man dieselben Übergänge auch im anderen Automaten machen kann. Die Anzahl der Schritte ist dann proportional zur Anzahl der Kanten. Die Anzahl der Kanten ist aber maximal z*n, falls z die Anzahl der Zeichen in \Sigma und n die Anzahl der Knoten (Zustände) ist. Damit ist das ein Polyzeitalgorithmus. (Details kannst du ja selbst ausführen.)

Never, ever reuse a paper abstract for a presentation, except if the abstract is “We show P = NP” or “We show P != NP”. If your abstract is one of the above two, double-check whether your proof is correct.
-- User’s Guide to the Beamer Class

Go to the top of the page

broetchen

Praktikant

Posts: 5

Date of registration: Apr 18th 2008

8

Friday, April 18th 2008, 6:41pm

Stimmt... das ist einleuchtend. Vielen Dank! :thumbsup:

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 müßte.

Bin kein Informatiker und deshalb nicht so geübt im Algorithmus schreiben... :whistling:

This post has been edited 1 times, last edit by "broetchen" (Apr 18th 2008, 7:00pm)

Go to the top of the page

broetchen

Praktikant

Posts: 5

Date of registration: Apr 18th 2008

9

Friday, April 18th 2008, 7:06pm

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!