Warum sind linear begrenzte Automaten nicht so beliebt wie andere Automaten?

9

Nach meiner Erfahrung werden kontextsensitive Sprachen und linear begrenzte Automaten in Kursen zur Berechenbarkeitstheorie häufig übersprungen oder übersprungen und sogar in einigen bemerkenswerten Lehrbüchern weggelassen, obwohl endliche und Pushdown-Automaten viel Aufmerksamkeit erhalten. Sicherlich muss es einen guten Grund geben, warum LBAs weniger fokussiert werden als ihre Kollegen?

computability fl.formal-languages automata-theory goric
quelle
Siehe diese Frage: Ist die Chomsky-Hierarchie veraltet?
Kaveh
Könnten Sie näher erläutern, wie sich die verknüpfte Frage bezieht, Kaveh? (Weil ich nicht denke, dass sein Ton hier hilfreich ist, aber individuelle Antworten könnten sein)
Raphael
2
@Raphael: Die Antworten auf die Frage, die Kaveh verlinkt hat, um zu erklären, warum kontextsensitive Sprachen nicht mehr so ​​wichtig sind wie zuvor: Kurz gesagt, es gibt andere, interessantere Modelle, die berücksichtigt werden müssen. (mehr)
Tsuyoshi Ito
2
(Fortsetzung) Der gleiche Grund gilt für "linear begrenzte Automaten". Es ist lustig, dass ich noch nie von diesem Namen gehört hatte. Für mich sind sie nur deterministische / nicht deterministische Turing-Maschinen im O (n) -Raum, und ich kann nicht verstehen, warum wir O (n) -Raum-Maschinen herausgreifen sollten (anstelle des Polynomraums oder des O (log n) -Raums oder was auch immer). obwohl es einen historischen Grund gegeben haben muss. Außerdem wird weder die Klasse DSPACE (O (n)) noch NSPACE (O (n)) unter Unterprogrammaufrufen geschlossen .
Tsuyoshi Ito
1
Tsuyoshi, meine Interpretation der Frage ist, dass FA, PDA und der Rest der Chomsky-Hierarchie (nach Ihrer / der Argumentation der Antworten ebenso langweilig) unterrichtet werden, LBA jedoch nicht.
Raphael

Antworten:

13

Mit "geeigneten" Modifikationen können wir diese Klassen in Komplexitätsklassen umwandeln; Endliche Automaten in , CFL in LogCFL und LBA in PSPACE.NC1

Es sollte jetzt ganz klar sein, warum wir uns mehr für die ersten beiden als für LBA interessieren. Die ersten beiden passen natürlich in die übliche Definition der realisierbaren Berechnung. PSPACE jedoch nicht.

V Vinay
quelle
1
Das Verwandeln eines LBA in PSPACE klingt fast so, als ob ein linearer Raum alles ist, was Sie benötigen, um PSPACE zu erfassen, was eindeutig nicht wahr sein kann. Was ist mein Denkfehler?
Suresh Venkat
2
@ Suresh: Es gibt die folgenden Verbindungen. Die Klasse von Problemen, die (NC1-) auf reguläre Sprachen reduzierbar sind, ist NC1, die Klasse von Problemen (log-space-), die auf CFL reduziert werden kann, ist LogCFL und die Klasse von Problemen (NC1- oder log-space-), die auf LBA reduziert werden können ist PSPACE. Ich bin mir nicht sicher, ob wir in all diesen drei Fällen den gleichen Begriff der Reduzierbarkeit verwenden können.
Tsuyoshi Ito
Ein vollständiges Problem für eine andere Klasse (auch unter Reduzierungen) zu enthalten, scheint kein guter Grund dafür zu sein, dass die Klasse interessant ist. AC0
Kaveh
3

Fragen Sie Ihren Professor, warum er es getan hat. Ich kann nur raten.

Sie sind nicht so interessant wie Turing-Komplettmodelle und PDAs, weil sie in der Leere der Nutzlosigkeit sind *, die sie natürlich mit ihrem Sprachäquivalent teilen: nicht so mächtig wie möglich, aber bereits sehr unlösbar.

Ein weiterer Grund könnte sein, dass nicht so viel über sie bekannt ist (hier erraten), aber das könnte auf ein Hühnerei-Problem zurückzuführen sein.

Es ist unklar, ist, was zu Problemen für die Didaktik führen kann. Außerdem sind typische Beweise (z. B. akzeptierte Sprache, Modelläquivalenzen) viel schwieriger als bei anderen Modellen.NLBA=DLBA

(*) absichtliche Übertreibung

Raphael
quelle
2

Es scheint, dass nicht nur CSG, sondern auch CFG, ... heutzutage aus der Mode sind. Ich denke, heutzutage werden Automaten und PDAs normalerweise in Kursen zur Berechenbarkeits- / Komplexitätstheorie (wenn überhaupt) gedacht und dort nicht für sich selbst, sondern zur Einführung von Turing-Maschinen aufgenommen.

Grammatiken sind wahrscheinlich interessant für die Compilertheorie, aber weniger für die Berechenbarkeit / Komplexität, die in einem Einführungskurs enthalten sein soll. Es gibt zu viele Themen, die man behandeln möchte, aber ein Semesterkurs ist einfach zu kurz und wir müssen auswählen, und viele dieser Themen, die wir aus zeitlichen Gründen nicht behandeln können, sind viel interessanter als LBA.

Kaveh
quelle
1
Ich wünschte du wärst allgemein wahr! Die in meiner Universität unterrichtete Intro-Klasse zu TCS besteht aus halben Automaten / CFL. Ich nehme an dieser Klasse teil und die Schüler scheinen wirklich weit davon entfernt zu sein, interessiert zu sein. Dies kann ein weiterer Grund sein, warum CFL / CSL nicht mehr vorgestellt werden: Es gibt Themen, die viel spannender sind.
Michaël Cadilhac
1
Nun, CS-Theorie ist nicht nur Komplexität. Insbesondere CFG sowie verwandte Automatenmodelle sind in vielen Bereichen der CS sehr wichtig (zumindest als Grundlage). Ein Einführungskurs sollte Sie auf alle Branchen vorbereiten. Entschuldigung, aber diese Antwort riecht nach Unwissenheit. Auch beantwortet es die Frage nicht.
Raphael
@ Raphael, ich spreche von Kursen zur Berechenbarkeits- / Komplexitätstheorie , in denen die Automatentheorie an Universitäten gedacht wird, die ich gerade kenne. Niemand sagte etwas über Theoriekurse im Allgemeinen. Ich denke, Sie sollten die Beiträge sorgfältig lesen, bevor Sie andere der Unwissenheit beschuldigen. Mein Beitrag beantwortet die Frage: Warum wird LBA nicht in Kursen zur Berechenbarkeits- / Komplexitätstheorie berücksichtigt? Das ist der Grund, und das ist der Grund, warum Lehrbücher zur Berechenbarkeits- und Komplexitätstheorie nicht viel über LBA enthalten, ob Sie es mögen oder nicht.
Kaveh
Sie kennen also die persönlichen Gründe jedes Autors und Dozenten auf der ganzen Welt? Ja richtig. Bitte beachten Sie jedoch, dass das Wort "Komplexität" in der gestellten Frage überhaupt nicht vorkommt. Beachten Sie auch, dass Sie durch den obigen Kommentar und die Bearbeitung von theprise die Frage nicht beantwortet haben. Fakt ist, ob es dir gefällt oder nicht.
Raphael
1
@Raphael, Sie lesen immer noch nicht sorgfältig und interpretieren das, was ich schreibe, weiterhin so, wie Sie es bevorzugen. Es scheint mir, dass Sie nur argumentieren möchten. Ich denke, mein Standpunkt ist klar genug. Denken Sie also frei, wie Sie möchten. :)
Kaveh
2

Reguläre Ausdrücke und CFGs werden in der Praxis zum Parsen von Code (dh Programmiersprachen) verwendet. Der Grund ist, dass es sehr effiziente Algorithmen gibt, um sie zu analysieren. LBAs hingegen sind zu leistungsfähig, um sie in diesem Kontext tatsächlich zu verwenden.

Ein historischer Ursprung der Automatentheorie ist das Thema der Compilerkonstruktion. Aus dem oben genannten Grund sind nur reguläre Sprachen und CFGs zum Erstellen von Compilern nützlich (ungeachtet der Tatsache, dass attributive Grammatiken nicht wirklich CFGs sind und dass CFG-Parsing-Algorithmen nicht wirklich die gesamte Klasse von CFGs analysieren). LBAs könnten von Chomsky als ein mittleres Maß an Komplexität zwischen dem Alltäglichen und dem "Englischen" erfunden worden sein. Vielleicht ist der richtige Ort, um sie zu unterrichten, eher ein Sprachkurs als ein Informatikkurs!

Yuval Filmus
quelle
Da LBAs der ganz natürlichen Klasse kontextsensitiver Grammatiken entsprechen, glaube ich nicht, dass sie nur zum Spaß erfunden wurden. ;)
Raphael
@ Raphael: Yuval hat das überhaupt nicht impliziert.
Reinierpost