Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
An alle Theo. Inf. Nachschreiber!!!
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, September 27th 2005, 4:59pm
Das einfache ist es, bei sowas erstmal einen NEA zu bauen und diesen dann in einen DEA umzuwandeln.
Quoted
Original von hohly
hi, sagt mal wenn ich einen DEA baue, der sagen wir mal das wort xabcy akzeptieren soll, gibt es da ein trick dabei?
http://www.thi.uni-hannover.de/lehre/ss05/ka/aktuell/
p.s. wann findet die klausur statt?wegen der kobmi mit der komplexität?
Wednesday, September 28th 2005, 10:42am
Wednesday, September 28th 2005, 2:50pm
noch ne frage wie zeige ich dass die sprache ww die nur aus a's besteht nicht regulär ist. ich denke mir dass man da zeigen soll dass es eine ungerade anzahl von a's entseht. hab dann soweit ausformuliert dass bei mir a^n+(i-1)l a^n steht. jetzt muss ich ja ein i wählen so dass die anzahl von a's ungerade wird, aber ich komme nicht drauf, weil ja l nicht fest ist sondern jeweils l>=1.
Guck doch mal im Schöning auf S.62 oben. Da steht: Jede kontextfreie Sprache über einem 1-elementigen Alphabet ist bereits regulär.
Wednesday, September 28th 2005, 3:14pm
Original von Kasi
1) Darf ich in Kellerautomaten "Epsilons" auf dem Band und im Keller lesen, wie auf Seite 70 unten im Schöning? Habe das mal bei ner Hausübung negativ angekreidet bekommen.
2) Muss ich, wenn ich es nicht darf (siehe 1)), das unterste Zeichen, z.B. als A-Quer, markieren, oder kann ich auch alles ohne ein A-Quer lösen?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 3:31pm
Das zeigt man gar nicht, da eine solche Sprache genau die Wörter mit gerader Länge umfaßt, die nur aus a's bestehen. Und diese Sprache ist regulär.
Original von hohly
noch ne frage wie zeige ich dass die sprache ww die nur aus a's besteht nicht regulär ist.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 3:36pm
Man kann Kellerautomaten auch so definieren, daß Epsilon-Übergänge erlaubt sind. Für diese Lehrveranstaltung haben wir uns jedoch entschieden, Kellerautomaten so zu definieren, daß immer ein Zeichen der Eingabe gelesen werden muß. Dies macht den Zusammenhang zu endlichen Automaten klarer, da dort auch immer genau ein Zeichen gelesen werden muß. Ein Kellerautomat ist also ein um einen Keller/Stack/Stapelspeicher ergänzter endlicher Automat.
Original von Kasi
1) Darf ich in Kellerautomaten "Epsilons" auf dem Band und im Keller lesen, wie auf Seite 70 unten im Schöning? Habe das mal bei ner Hausübung negativ angekreidet bekommen.
Die Markierung des letzten Zeichnens auf dem Speicher ist in der Regel nötig, um in diesem Fall in einen akzeptierenden Zustand wechseln zu können.
2) Muss ich, wenn ich es nicht darf (siehe 1)), das unterste Zeichen, z.B. als A-Quer, markieren, oder kann ich auch alles ohne ein A-Quer lösen?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 3:41pm
Dies gilt nur zu Beginn der Rechnung. An dieser Stelle kann das Bottom-Symbol (#) ja durch etwas anderes ersetzt werden.
Original von EnteTaylor
Das unterste Kellersymbol ist allerdings immer #.
Nein. Gemäß der Definition von Kellerautomaten aus der Vorlesung akzeptiert ein Kellerautomat genau dann, wenn nach dem Lesen des letzten Zeichens der Eingabe ein Endzustand erreicht wird. Bleibt der Automat vorher stehen (weil der Speicher leer ist), so wird nicht akzeptiert.
Ein Wort wird immer dann akzeptiert, wenn der Keller leer ist.
Wednesday, September 28th 2005, 4:36pm
Original von Joachim
Original von EnteTaylor
Nein. Gemäß der Definition von Kellerautomaten aus der Vorlesung akzeptiert ein Kellerautomat genau dann, wenn nach dem Lesen des letzten Zeichens der Eingabe ein Endzustand erreicht wird. Bleibt der Automat vorher stehen (weil der Speicher leer ist), so wird nicht akzeptiert.
Ein Wort wird immer dann akzeptiert, wenn der Keller leer ist.
Man kann Kellerautomaten auch so definieren, daß sie akzeptieren, wenn der Keller leer ist. Diese Definition haben wir jedoch in dieser Lehrveranstaltung nicht gewählt, um die Parallelen zu endlichen Automaten klarer zu machen.
Da haste wohl recht. Hatte die Definition aus dem Schöning genommen, mir ist jetzt erst aufgefallen, dass im Buch ein Kellerautomat ein 6-Tupel und in der Vorlesung ein 7-Tupel (wegen der Endzustände) ist. Ich hoffe, dass jetzt niemand verwirrt wurde..
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 5:53pm
Wenn x2 - x4 = 0 gilt, kann es auch sein, daß x2 < x4 gilt. Negative Zahlen gibt es in LOOP-Programmen ja nicht, statt der Subtraktion wird die "modifizierte Subtraktion" verwendet, d. h. negative Ergebnisse werden zu 0.
Original von hohly
und noch ne frage
LOOP x1 DO
x2:=x1;
x3:=x3+1;
x4:=x3*x3;
x2:=x2-x4;
IF x2=0 THEN
x4:=x4-x1;
IF x4=0 THEN x0:=1 END
END
END
ich versteh nicht ganz was die
IF x2=0 THEN
x4:=x4-x1;
machen soll? ich gucke doch nach ob x2-x4=o ist, dass heisst ich habe die gesuchte quadratzahl, wieso setzte ich nicht danach einfach x0:=1 und das wars?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 5:56pm
Das steht alles im Skript (dort, wo die verschiedenen Typen von Grammatiken definiert werden).
Original von Kasi
3) Wie wurde es mit den "Epsilons" bei den Grammatiken in der Vorlesung gehandhabt? Schöning macht es so:
S --> Epsilon | S'
S' --> A | B (S nicht auf der rechten Seite)
4) Ist das "Epsilon" in Typ-1 bis 3-Grammatiken an jeder Stelle erlaubt (außer Epsilon --> Epsilon vielleicht)? Oder gibt es Einschränkungen?
Wednesday, September 28th 2005, 6:28pm
Original von Joachim
Das zeigt man gar nicht, da eine solche Sprache genau die Wörter mit gerader Länge umfaßt, die nur aus a's bestehen. Und diese Sprache ist regulär.
Original von hohly
noch ne frage wie zeige ich dass die sprache ww die nur aus a's besteht nicht regulär ist.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 28th 2005, 6:37pm
Wenn Du eines der Pumping Lemmata dazu verwenden willst, um zu zeigen, daß eine Sprache nicht regulär bzw. nicht kontextfrei ist, mußt Du ein Gegenbeispiel konstruieren, das die im jeweiligen Pumping Lemma geforderten Eigenschaften nicht besitzt. Und wenn Du davon überzeugt bist, daß eine Sprache nicht regulär bzw. nicht kontextfrei ist, Dein bisher gewähltes Wort aber nicht als ein solches Gegenbeispiel zu gebrauchen ist, mußt Du es natürlich mit einem anderen Wort versuchen. Eine feste Regel, wie solche Gegenbeispiele "typischerweise" aussehen, gibt es nicht.
Original von hohly
Original von Joachim
Das zeigt man gar nicht, da eine solche Sprache genau die Wörter mit gerader Länge umfaßt, die nur aus a's bestehen. Und diese Sprache ist regulär.
Original von hohly
noch ne frage wie zeige ich dass die sprache ww die nur aus a's besteht nicht regulär ist.
ja aber ww dass aus a's und b's bestehen darf?
ich kann doch das wort a^na^n oder auch a^nb^na^nb^n machen. somit
wäre ein a^na^n regulär aber a^nb^na^nb^n nicht?
wenn das alphabet aus a's und b's besteht muss ich auch für das wort a und b benutzen? oder kann ich auch nur a oder b nutzen?
