Automatentheorie – die neusten Beiträge

Was heißt es:

man kann jedes Problem in P auf jedes andere Problem in P reduzieren

?

Angenommen als Beispiel:

• L1 ist die Entscheidung, ob eine Zahl z1 gerade ist
• L2 ist die Entscheidung ob eine Zahl z2 prim ist

Ich kann nun spaßhalber eine Reduktion von L1 -> L2 machen, indem ich

zuest L1(z1) löse und wenn das Ergebnis

• ja ergibt, füttere ich L2 mit dem Input 3
• nein ergibt, füttere ich L2 mit dem Input 6

Dann habe ich L1 in Polyzeit auf L2 reduziert: man schreibt



bzw. man sagt

" L2 ist mindestens so schwierig wie L1"

Ich könnte aber auch umgekehrt eine Reduktion von L2 -> L1 machen, indem ich

zuest L2(z2) löse (wie auch immer, aber eben in Polyzeit) und wenn das Ergebnis

• ja ergibt, füttere ich L1 mit dem Input 2
• nein ergibt, füttere ich L1 mit dem Input 1

Dann würde ich schreiben können:



bzw. sagen

L1 ist mindestens so schwierig wie L2"

Das würde bedeuten, dass P1 und P2 gleich schwierig sind, was aber klarerweise nicht der Fall ist. Hab ich da was falsch verstanden?

Wie ist das also diese Notation zu interpretrieren?? Irgendwas stimmt doch hier nicht...wo bin ich falsch abgebogen?

Die Turing-Maschine ist scheinbar ein wichtiges Konzept in der theoretischen Informatik. Ich selbst bin ein kompletter Laie in der Informatik, habe aber in anderen Zusammenhängen immer wieder davon gehört. Bisher habe ich aber nie verstanden, wozu man das Konzept einer "nicht-deterministischen Turing Maschine" (NTM) benötigt: Soweit ich laienhaft verstanden habe, tut man so, als könne diese NTM Ergebnisse für eine Eingabe quasi erraten (Orakel) und dann schnell auf Akzeptanz prüfen. Was meint man hier mit erraten? Wo ist der konzeptionelle Unterschied zu deterministischedn TMs? Auch dort kann ich ja auf beliebig viele Berechnungspfade aufspalten (Speicher ist ja unbegrenzt) und quasi "parallel" rechnen. Es geht ja bei NTM nicht darum wie effizient diese sind - aber dann verstehe ich nicht, was daran so interessant ist.

Kann mir jemand ein konkretes Beispiel liefern, sodass ich den Vorteil des Konzepts erkennen kann?

Der gezeigte NFA muss in einen DEA umgewandelt werden. Ich bin mir aber nicht sicher, ob ich dann bei {q2,q3} q2 als neuen Zustand einführen muss. Gleiche Frage gilt für die anderen nicht abgeschlossenen Übergänge.

Vorab: Es geht um Reguläre Ausdrücke im Sinne der theoretischen Informatik.

Der "+"-Operator ist doch bei Anwendungen von Reguläre Ausdrücke wie ein XOR zu betrachten. "a+b" enthält die Wörter a und b aber nicht ab. (a+b)* würde a,b,ab,abab... wiederum enthalten. Oder sehe ich das falsch?

Bei Flaci, das ist ein Tool für sowas, ehemals auch AtoCC wird mir bei a+b nur ab als Wort der Sprache L angezeigt

a* a|b ab sind reguläre Ausdrücke. Hier die Aufgabe:

Wie geht man bei a) sowie b) am besten vor? Um den regulären Ausdruck zu erzeugen?

In der Regel geht man so vor, das man aus einer Sprache L(G) mit einer Grammatik einen NFA(Nichtdeterministischen Automaten) konstruiert. Dann aus dem NFA eine DFA (Deterministischen Automaten) und daraus wieder die Sprache mit Ihrer Grammatik ableitet L(G).

L(G) zu NFA zu DFA zu LG?

Was ich mich jetzt Frage ist, kann man auch anders herum vorgehen, d. h. man aus einer L(G) einen DFA und aus diesem dann einen NFA und daraus leitet man wieder seine Grammatik ab?

Oder ist diese Vorgangsweise um einiges komplizierter als von

LG zu DFA zu NFA zu LG

Hallo, ich bin auf eine schwierige Aufgabe bezüglich des Pumping Lemmas für reguläre Sprachen gestoßen und ich komme nicht weiter bei der Zerlegung eines Wortes s in xyz. Es handelt sich um die Sprache L = {a^n b^m c b^m a | n, m aus den natürlichen Zahlen}.

Ich hatte als s ursprünglich a b^p c b^p a gewählt, aber ich verstehe nicht, wie man hieraus einen Widerspruch formen kann, denn wenn sich y bloß aus a's zusammensetzt, wird das Pumping Lemma hier ja erfüllt.

Danke im Voraus!

Hallo,

meine Idee ist es automaten für verschiedene Waren auf einem LKW zu installieren, und dann zu verschiedenen Events zufahren.

Die Frage ist jetzt als was zählt das was brauch ich rechtlich?

LG

Kann mir jemand bei Aufgabe 8 a) helfen? Ich verstehe nicht, wie ich die Grammatik entwickeln soll. Es sollen Ausdrücke wie 089-KP7 rauskommen, steht ja am Anfang wie, weiß nur nicht wie ich es umsetzen soll. Danke im Voraus.

Hallo, ich habe folgende Sprache:

L3 = {w | w hat eine gerade länge UND eine ungerade Anzahl von 0 } wie sieht der DEA aus?

Hallo

falls ihr das schon gemacht habt, ist das schwer? Bruacht man da viel aufwand?

Ich habe mal gehört dass sich da viele irgendwie die Zähne ausbeißen aber eigentlich ist das mit den Automaten ja ziemlich leicht.

Kann mih da wer aufklräen? Wie schwer ist das ca?

lg

Guten Abend,
ich sitze nun schon mehr als 3 Stunden an dieser Sprache inklusive Alphabet hier:

Hat Jemand eine Idee?
Klar ist, dass die Sprache entweder mit Lambda oder mit 11 oder mit 10 oder mit 00 terminiert. Nur bin ich gerade irgenwie nicht in der Lage etwas passendes zu finden, Fällt euch was schnelles ein?
Liebe Grüße

P.S. Es ist keine Hausaufgabe, also eine vollständige Lösung wäre auch erwünscht.