Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Falls 1. damit gemeint ist (weiß es auch nicht …), dann könntest du einen “Beweis” angeben. Für A,B z.B. 0, da B mit einer 0 im Endzustand D landet, A aber in B, wobei wiederrum B und D nicht gleich sein können wegen epsilon. Quasi einen Teil des NEQ Algo hinschreiben …
sollen wir da etwa jeweils A und B und dann A und C miteinander vergleichen?
ich dachte vielmehr, die elemente {A,B} und {A,C} aus der potenzmenge miteinander…
Es war nach Zeugen = „Eingabewörte“ für (Nicht-) Äquivalenz gesucht. @Otis: Es sollte A mit B unc A mit C verglichen werden.
Ich habe es so gemacht, und es gab entsprechend Punkte…
Bei der Aufgabe 4 Minimierung von A2, wollte ich mal Fragen, ob man den Zustand E, nicht auch weglassen kann im minimierten Graph. Weil aus E kann ich eh nicht mehr rauskommen und E ist ja kein Endzustand. Oder muss ich E trotzdem mit hinschreiben, damit ich von jedem Zustand aus für 0 und 1 eine Kante hab. Andererseit ist doch der Minimalautomat so, dass es keinen anderen AUtomaten gibt der die gleiche Sprache akzeptiert und weniger Zustände hat, aber wenn ich den Zustand E weglass hab ich doch immer noch einen Automaten, der die selbe Sprache akzeptiert…
Wie macht ihr das mit solchen Zuständen?
Das war in der Vorlesung unklar.
Um einen Minimalautomaten zu erreichen müssen in der Tat auch noch tote Zustände entfernt werden, zur Minimierung zählt das glaube ich aber nach Vorlesung nicht.
Ein Kommentar von rwanka wäre hier interessant ;).
Darf man fuer p eigentlich einen festen Wert nehmen?
Natuerlich muss der Wert dann fuer jede beliebe Groesse von z gelten.
So habe ich das naemlich gemacht…
Oder muss ich p allgemein halten?
Weil, wenn ich ich p einen Wert zuweise und dieser aber immer fuer die reg. PE passt, dann sollte das doch erlaubt sein oder?
Wenn du zeigen willst, dass eine Sprache die reguläre Pumpeigenschaft besitzt reicht ein festes p, ja. Ein allgemeines p brauchst du eben, wenn du das Gegenteil zeigen willst, also dass eine Sprache die reguläre Pumpeigenschaft nicht besitzt.
Sei p beliebig aber fest. Setze z=1^p 0^p ∈ L, |z| ≥ p.
Sei u,v,w beliebig aber fest:
Aus: |uv| ≤ p folgt, dass u und v nur 1en enthalten
Aus: v ≠ ε folgt, dass v mindestens eine 1 enthält.
Setze i = 0: Da v mindestens eine 1 enthält wird diese weggepumpt. Die Anzahl der 0en passt danach nicht mehr zur Anzahl der vorangehenden Zeichen, also ist z=uv^i w ∉ L => L hat reg. PE nicht.
Tote Zustände könnten vorher erkannt und gelöscht werden. Hinterher können Sie sagen: Diese Zustände hier tragen nichts zur Sprache bei und könnten auch weggelassen werden. Allerdings ist δ dann nicht total und man braucht die (übliche) Konvention, daß man dann verwerfend abbricht. Also: dalassen und einen Hinweis. Zum Glück lesen echte Menschen die Klausur und keine TMs.