theoretische Informatik regulärer Ausdruck klasse p

Klasse P und reguläre Ausdrücke

Von: , 27.06.2011 15:46 Uhr

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?

1 Antworten zu dieser Frage

- - Antwort von - abgemeldetes Mitglied - nach 170 Tagen 0 hilfreich
    
    Re: Klasse P und reguläre Ausdrücke
    
    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.
    
    Jetzt auf diese Frage antworten.