Hallo liebe Fachleute. Meine Frage wäre: Sind alle Sprachen in P durch einen regulären Ausdruck beschreibbar?
Ich weiß, dass die Klasse P Probleme beschreibt, die in polynomialer Zeit gelöst werden können und dass reguläre Ausdrücke reguläre Sprachen beschreiben.
Also müssten laut meiner Fragestellung alle Sprachen in P regulär sein. Ist das der Fall?
Nein. Reguläre Sprachen lassen sich durch einen endlichen Automaten entscheiden, d.h. also in linearer Laufzeit n.
In P gibt es jedoch komplexere Sprachen. Ein noch ganz einfaches Beispiel, von dem oft gezeigt wird, dass es nicht regulär ist, ist a_n b_n c_n
Gruß, mofte
Also sind endliche Automaten immer O(n) und es kann Sprachen in P geben, die O(n²) sind?
Dann wären Reguläre Sprachen ja eine Teilmenge der Klasse P richtig?
Hallo,
die Argumentation hört sich plausibel an; aber das Grundstudium ist schon viel zu lange her…
Sorry
Also sind endliche Automaten immer O(n) und es kann Sprachen
in P geben, die O(n²) sind?
Ja, die gibt es. Sortieren in n*logn, vieles auch in n*n*n oder noch höher.
Dann wären Reguläre Sprachen ja eine Teilmenge der Klasse P
richtig?
Ja.
Gruss, mofte
Hallo,
nur die wenigsten Sprachen in P sind regulär. Die Klasse P entspricht der vollen Berechnungskraft einer Turingmaschine in Polynomialzeit. Reguläre Sprachen werden von endlichen Automaten in Linearzeit entschieden.
Die Sprache {a^nb^n|n>1} ist z.B. nicht regulär (Siehe Pumping Lemma) kann aber von einer Turingmaschine leicht in polynomieller Zeit entschieden werden.