Reguläre Grammatik vs regulärer Ausdruck?

Hallo,

ich arbeite gerade das Buch Compiler Engineering von Cooper durch und habe schon mehrere Fragen dazu. Vllt gibt es ja einen ITler, der mir helfen kann.

Im zweiten Kapitel habe ich reguläre Ausdrücke kennengelernt, mit welcher man eine reguläre Sprache beschreiben kann.

Der Scanner erzeugt also Wörter, die an den Parser weitergegeben werden.

Frage 1: Jetzt arbeitet der Parser mit einer regulären Grammatik, um eine Syntaxanalyse durchzuführen. Zu Beginn dachte ich, bei den Terminalen handelt es sich um Wörter aus der Sprache, aber wenn ich es jetzt richig verstehe, sind Terminale Zeichen aus dem Alphabet, über welchem die Sprache gebildet wird.

Wie erzeugt der Parser daraus eine Syntaxprüfung, wenn nicht die Reihenfolge der Wörter, sondern die, der Buchstaben analysiert wird. Sind die Grammatiken denn so komplex, dass die Wortreihenfolge kontrolliert werden kann? Bzw. wieso werden für beide Phasen dann nicht einfach eine Grammatik oder RegExes genutzt, anstatt beides zu definieren?

Frage 2: Ich dachte immer, eine Reg Gram und eine RegEx wären unterschiedliche Dinge. Hier https://de.wikipedia.org/wiki/Regul%C3%A4re_Grammatik#Regul%C3%A4re_Sprachen und im Beitrag unter Regulären Sprachen, wird aber gesagt, dass dies beide äquivalente Konzepte sind.

Was mich daran stört.

Als nicht reguläre Sprache wird häufig die Sprache L = a^n b^n genannt. Mir ist zwar bewusst, dass ich die Sprache nicht durch eine RegEx oder einen Automaten abbilden kann (von denen mir bewusst ist, dass sie äquivalent sind), aber ich könnte doch mit einer Regulären Grammatik bspw. die Ableitungsregel S -> aSb | € (epislon soll das sein :P) erzeugen und hätte damit doch eine Beschreibung für die Sprache.

Wenn RegExes und RegGrams aber äquivalent sind, dann scheine ich ja einen Fehler in der Ableitung zu machen.

Frage 3: Definition Reguläre Sprachen https://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache#Definition

Hier wird beschrieben, dass eine der Bedingungen erfüllt sein muss, damit es sich um eine Reg Sprache handelt. Aber wenn eine Bedingung erfüllt ist, sind nicht gleichzeitig alle Bedingungen erfüllt?

Verwirrt mich alles ziemlich

Mathematik, IT, Informatik, Scanner, Theoretische Informatik, formale Sprachen, Regulärer Ausdruck
Wäre damit das P-NP Problem gelöst?

Also für alle, die nicht wissen, was es ist, es ist eines der Millenium Probleme, welches noch nicht gelöst wurde.

Kurze Zusammenfassung der Frage des P-NP Problems:

Bedeutet die Fähigkeit, korrekte Antworten schnell zu erkennen (NP) auch, dass es eine schnelle Möglichkeit gibt, diese Antworten zu finden (P)?

Beispiel:

Man hate einen Zauberwürfel mit auf jeder Seite hunderten Feldern, sobald er "gelöst" wird, kann man schnell erkennen, ob er richtig oder falsch gelöst wurde, allerdings würde man (nach dem heutigen Wissensstand) nahezu ewig brauchen, um ihn überhaupt lösen zu können, die Frage ist da halt: gibt es eine Möglichkeit, ihn schnell lösen zu können, da man ja auch schnell sehen kann, ob er richtig oder falsch gelöst ist.

Meine "Lösung" (als Gedankenexperiment; noch nicht rechnerisch nachgewiesen):

Man will ein Passwort hacken, weshalb man einen Algorithmus schreibt, welcher die Passwörter einzeln durchgeht (Problem in NP). Da wird ja schnell erkannt, ob ein Passwort richtig oder falsch ist (dadurch, dass man dann eingeloggt ist oder eben nicht), allerdings gibt es keine Möglichkeit, es anders herauszufinden, da es eben einfach keinen anderen Lösungsweg gibt. Also gibt es auch keinen schnelleren Lösungsweg, weshalb nur an diesem Beispiel theoretisch nachgewiesen wäre, dass P≠NP ist oder?

Ich würde mich über sachliche Antworten sehr freuen, mir ist bewusst, dass meine Antwort vermutlich viel zu einfach ist, damit sie als Lösung gesehen werden könnte und das andere Leute diese Idee vermutlich auch schon hatten. Mich würden nur eure Gedanken dazu interessieren!

Theoretische Informatik
Warum lässt sich jedes Problem in P auf jedes andere Problem in P reduzieren und was heißt das?

Ich habe gerade gelernt, dass man jedes Entscheidungsproblem L1 über Σ in P auf jedes andere Problem L2 über Σ aus P reduzieren kann. Mit hat es hier "die Kette rausgehauen":

Eine Reduktion ist ja eine berechenbare Abbildung



jetzt könnte ich festlegen Σ = Natürliche Zahlen von 1 bis 1 Million

L1 = {w ∈ Σ | w ist prim)

L2 = {w ∈ Σ | w ist gerade)

und definieren:

f(w) = 6 wenn w prim

f(w) = 7 wenn w nicht prim

Dies erfüllt genau die obige Definition einer Reduktion.

Nur welchen Sinn macht es, hier von einer "Reduktion" zu sprechen, denn ich habe ja den Primtest auf eine Zahl nicht auf den Test auf Geradheit einer Zahl zurückgeführt.

Ich hätte intuitiv etwas als Reduktion bezeichnet, wenn ich durch die Entscheidung L2 auch L1 entscheiden kann. Hier liegt aber aus meiner Laiensicht ein "fauler Zauber" vor, denn in der Abbildungsvorschrift f ist eigentlich schon enthalten, dass ich dafür schon die Entscheidung auf Prim durchführen, also L1 lösen muss. Es "hört sich aber so an", als könnte man nun einen Primtest (der ja, obwohl in P liegend, relativ komplex ist) auf etwas "reduzieren", wo man nur auf Geradheit prüft (was ja von der Komplexität nicht vergleichbar ist). Jedenfalls ist das nicht im Sinne der Erfindung eines "funktionierenden" Algorithmus für L1, den ich zu lösen vermag, indem ich L2 löse.

Ich hoffe, ich habe mich in meiner Notation verständlich ausgedrückt und man weiß, was ich meine...(bin kein Informatiker, daher bitte Milde walten lassen ;-)

Habe ich eine falsche Vorstellung von einer Reduktion oder ist das einfach so?

Informatik, Theoretische Informatik, formale Sprachen

Meistgelesene Beiträge zum Thema Theoretische Informatik