Welche Sprache wird benötigt, um eine geordnete Liste zu erkennen? [offenbar Mehrkopfautomaten]

Ich denke über das Problem nach, eine Sprache (über Alphabet 0-9 und Leerzeichen) zu erkennen, die Zeichenfolgen wie "1 2 3 4 5 6" und "14 15 16 17" enthält, aber nicht "1 3".

Dies geschah während der Arbeit an einer allgemeinen Analyseaufgabe, bei der Elemente in einer geordneten Liste enthalten sein mussten. Es fiel mir auf, dass das Parsen des Restes dieser Sprache zwar regelmäßig war, dieser Teil jedoch eindeutig unregelmäßig war - er kann beispielsweise die Sprache A1A2 erkennen, in der A eine beliebige Zeichenfolge 0-9 ist. Tatsächlich scheint es inhaltssensitiv zu sein (und durch das Pump-Lemma nicht kontextfrei).

Meine erste Frage: Gibt es eine (einigermaßen bekannte, dh nicht nur für dieses Problem definierte) Sprachklasse zwischen kontextsensitiv und kontextfrei, die ihre Ausdruckskraft besser beschreibt? Ich habe über Ahos indizierte Sprachen gelesen, aber es ist (für mich!) Nicht offensichtlich, dass diese sogar in dieser Klasse sind, obwohl sie mächtig sind.

Meine zweite Frage ist informell. Es scheint, dass diese Sprache leicht zu analysieren ist, und dennoch steht sie in der Hierarchie ganz oben. Ist es üblich, auf ähnliche Beispiele zu stoßen, und gibt es eine Standardmethode, um mit ihnen umzugehen? Gibt es eine alternative Gruppierung von Sprachklassen, die nicht mit der Aufnahme in die "üblichen" Klassen vereinbar ist?

Mein Grund zu der Annahme, dass dies einfach ist: Die Sprache kann deterministisch analysiert werden, indem Sie lesen, bis Sie das Ende der ersten Zahl erreicht haben, prüfen, ob die nächste Zahl folgt, und so weiter. Insbesondere kann es in O (n) Zeit mit O (n) Raum analysiert werden; Der Raum kann auf O ( √) reduziert werdenohne zu viel Mühe, denke ich. Aber es ist schon schwer genug, diese Art von Performance mit normalen Sprachen zu erzielen, geschweige denn ohne Kontext.$O(\sqrt n)$

Es hört sich so an, als ob Sie nach Mehrkopfautomaten suchen (in Ihrem Fall sollten deterministische endliche Einwegautomaten mit zwei Köpfen ausreichen). Ich bin kein wirklicher Experte in diesen Bereichen, aber Google zeigt einige interessante Umfragen zu dieser Sprachhierarchie an, wie z

Marek Chrobak: Hierarchien von Einweg-Mehrkopfautomaten, http://www.sciencedirect.com/science/article/pii/0304397586900939

Dies gibt auch eine Antwort auf Ihre zweite Frage: Die Hierarchie der n-Kopf-Automaten liegt "über" die Chomsky-Hierarchie.