Die Gesamtlänge des Eingangs in einen Pushdown-Automaten, der von leerem Stapel akzeptiert, ist eine obere Grenze in den Zahlenzuständen und Stapelsymbolen

Question

Ich ging durch den klassischen Text "Einführung in die Automata-Theorie, Sprachen und Berechnung" (3. Ausgabe) von Jeffrey Ullman, John Hopcroft, Rajeev Motwani , wo ich auf wenige Aussagen über a gestoßen bin Pushdown-Automaten (PDA), das mit leerem Stapel akzeptiert, wie:

1. $ n $ , die Gesamtlänge des Eingangs ist sicherlich eine obere Grenze an der Anzahl der Zustände und Stapelsymbole. .

2. Eine Regel könnte fast n Symbole auf den Stapel platzieren.

Die folgenden Aussagen wurden gemacht, während die Autoren dabei einige Notizen über die Entscheidungseigenschaften von CFLs (Kontextfreie Sprachen) vornehmen würden (kontextfreie Sprachen)

Jetzt sind hier einige Punkte, von denen ich möglicherweise der Ansprüche widersprechen kann, anstatt es richtig zu beweisen.

.

1. Angenommen, $ N $ , ist die Gesamtlänge der Eingabe, aber gemäß dem Entwurf des PDA kann dies so passieren, dass die Eingabe akzeptiert wird Saite Alle Staaten der PDA sind nicht involviert, daher können wir nicht sagen, dass $ N $ eine obere Grenze in der Anzahl der Zustände ist, die die PDA hat.

2. Obwohl das PDA mit leerem Stapel akzeptiert, kann dies so passieren, dass eine Übergangsfunktion mehr als $ N $ Elemente auf der Oberseite des Stapels hinzugefügt wird, Am Ende nutzen Sie jedoch das Verbrauch von $ N $ Input-Symbole, auf dem jeweiligen Zustand bleiben und Epsilon-Übergänge verwenden, um einfach in demselben Zustand zu bleiben und die Elemente von der stapeln, bis es leer wird. Wie können wir also sagen, dass $ N $ eine obere Grenze an den Zahlenelementen auf dem Stapel ist? Wir kommen in einem Widerspruch an ...

Ich verstehe nicht, wohin ich den Fehler mache, denn die gleichen Aussagen werden in der 3. Ausgabe des Buches geschrieben, ohne dass Änderungen aus der zweiten Ausgabe erstellt werden, die es wahrscheinlich macht, dass die Anweisung korrekt ist. .

Ich habe den entsprechenden Teil des untenstehenden Textes angehängt:

Answer 1

Dieser Abschnitt spricht nicht über Analyse. Die genannten Algorithmen sind Algorithmen zum Umwandeln zwischen CFGs und PDAs verschiedener Typen. Die Frage ist, wie üblich, "was ist die rechnerische Komplexität des Algorithmus", und die Antwort ist, wie üblich in Bezug auf die Größe des Eingangs - an den Algorithmus ausgedrückt.

Der Eingang an einen Algorithmus, der eine PDA in ein CFG umwandelt, ist die PDA und die Größe des Eingangs - der Metrikstab für den Komplexität der Algorithmus - ist die Größe der * PDA ". Das ist das, was die Autoren beabsichtigen n zu sein.

Wie misst man die Größe eines PDA? Einfach: Sie schreiben das PDA als Zeichenfolge in eine PDA-Definitionssprache und zählen Symbole in der Beschreibung. Das ist ein völlig faires Verfahren, denn, um den Umwandlungsalgorithmus auf der PDA anzurufen, ist es notwendig, dem Konverter eine Eingabe anzugeben, die die PDA darstellt.

Angesichts dieser Definition sind die Ansprüche überhaupt nicht überraschend. Jeder Zustand und jedes Alphabet-Symbol muss mindestens einmal in der PDA-Beschreibung vorhanden sein, so dass die Größe, wenn diese Beschreibung eine obere Grenze ist. In ähnlicher Weise ist es möglich, dass der größte Teil der Beschreibung der PDA die Beschreibung einer einzelnen Regel ist, die fast generationspflichtige Symbole mitgenutzt.