4. Theoretische Informatik: Reguläre Sprachen ich bin verwirrt

Theoretische Informatik: Reguläre Sprachen ich bin verwirrt

  • ?

    Hallo,

    ich lese seit längerem das Buch "Introduction to the Theory of Computation", am Anfang bei den endlichen Automaten steht:

    A language is called regular language if some finite automaton recognizes it.

    Dann später wird das Pumping Lemma erklärt u.a. steht da:

    If we can show that a language does not have this property, we are guaranteed that it is not regular.

    Das Pumping Lemma wird dann auch auf der Sprache L(A) = { (0k1k | k >= 0 } angewandt um zu zeigen das sie nicht regulär ist. Was sie doch auch ist oder?

    Dann habe ich weitergelsen und bin irgendwann zum Kapitel "Time Complexity" gekommen. Da wurde gezeigt das es eine Turing Maschiene gibt die die Sprache L(A) = { (0k1k | k >= 0 } entscheided in o(nlog(n)).

    Und dann steht da:

    In fact, any language that can be decided in o(nlog(n)) time on a single-tape Turing machine is regular

    Jetzt bin ich total verwirrt da ich immer davon ausgegangen bin das L(A) = { (0k1k | k >= 0 } NICHT regulär ist.

    Habe ich das ganze Buch jetzt falsch verstanden oder habe ich einen Denkfehler?

    Besten Dank
    🙂

    0
  • O

    Erstmal: Die Sprache ist nicht regulär. Dafür braucht man eine Maschine, die "zählen" kann, also Ableitungen der Form S->0S1 erzeugt. Aber das geht mit regulären Grammatiken nicht.

    Das Buch widerspricht sich da also, und nebenbei ist es sehr einfach zu beweisen, dass sich eine reguläre Sprache in O(n) parsen lässt(sofern n die Länge des Wotes ist...)

    0
  • L

    Wie sieht denn die single-tape Turning Maschine aus, die die Sprache in o(n log n) entscheidet?

    0
  • ?

    Die Turingmaschiene faehrt ueber das Band und streicht immer die Haelfte der Nullen und Einsen weg und macht dann irgendwas mit Parity bits. Kann ich gerade nicht nachschauen da ich das Buch nicht zu Hand habe.
    Spaeter wird dann die Turing Machine vorgestellt die die Sprache in O(n) entscheidet wie otze gesagt hat.

    Aber das ist auch nicht mein Punkt ich haenge einfach an dieser Formulierung fest

    In fact, any language that can be decided in o(nlog(n)) time on a single-tape Turing machine is regular.

    0
  • O

    Die Aussage scheitert ja bereits daran, dass viele Kontextfreie Sprachen (LL(k), LR(k)) in O(n) entscheidbar sind. Ich denke, das ist einfach ein Fehler im Buch. Haste schonmal überprüft, ob es vielleicht irgendwo eine Errata dazu gibt?

    0
  • K

    otze schrieb:

    Die Aussage scheitert ja bereits daran, dass viele Kontextfreie Sprachen (LL(k), LR(k)) in O(n) entscheidbar sind.

    Mit einer Einband-Turingmaschine? Kannst du ein Beispiel nennen?

    0
  • O

    knivil schrieb:

    Mit einer Einband-Turingmaschine? Kannst du ein Beispiel nennen?

    Erinnere ich mich falsch aus TI oder ist nicht jeder While-Sprache so auf Einband-Turing Maschinen simulierbar, dass die Laufzeit des Algorithmus erhalten bleibt?

    (kann mich da natürlich auch irren, ist halt auch schon 2 Jahre her...)

    0
  • J

    otze schrieb:

    knivil schrieb:

    Mit einer Einband-Turingmaschine? Kannst du ein Beispiel nennen?

    Erinnere ich mich falsch aus TI oder ist nicht jeder While-Sprache so auf Einband-Turing Maschinen simulierbar, dass die Laufzeit des Algorithmus erhalten bleibt?

    (kann mich da natürlich auch irren, ist halt auch schon 2 Jahre her...)

    Die Laufzeit ändert sich nur um einen polynomiellen Faktor, gleich bleibt sie aber nicht. Das Problem mit dem einen Band ist, dass der Lesekopf ständig hin- und herfahren muß, um die 1er gegen die 0er abzuwägen. Ich denke nicht, dass man die gesamte abzufahrende Wegstrecke unter nlogn gedrückt kriegt.

    edit: beispielsweise ist recht klar, dass man um Palindrome zu erkennen auf einer Turingmaschine mit einem Band (und nur einem Lesekopf) quadratische Zeit benötigt. Mit ner while-schleife lässt sich das aber bequem formulieren so dass es auf ner Standard-Maschine (RAM oder so) in Linearzeit läuft.

    0
  • O

    Danke dir 🙂

    Naja, unabhängig davon, kann man wirklich sagen, dass Reguläre Sprachen in O(n) interpretiert werden.

    Konstruktiver Beweis:
    Algorithmus der aus jedem DFA M eine äquivalente Turingmaschine T erzeugt

    Für alle Zustände zi aus M
   Erzeuge Zustand Zi in T
Für alle Zustände zi aus M
   Für alle Folgezustände zj aus zi mit Zeichen a
       Erzeuge in Zustand Zi Übergang (Zj,a,R)

    Fertig. Die Maschine ließt immer ein Zeichen und macht auf Basis dieses Zeichens einen Deterministischen Schritt in den Zuständen(die damit einen DFA simulieren). Und damit ist das O(n).

    0
Anmelden zum Antworten