Ich las über Iota und Jot und fand diesen Abschnitt verwirrend:
Im Gegensatz zu Iota, wo der syntaktische Baum für einen String entweder links oder rechts verzweigt sein kann, ist die Jot-Syntax einheitlich links verzweigt. Infolgedessen ist Iota streng kontextfrei, aber Jot ist eine reguläre Sprache.
Mein Verständnis ist, dass sowohl Iota als auch Jot vollständig sind. Aber anscheinend ist einer kontextfrei und der andere regelmäßig! Sicherlich können reguläre Sprachen nicht vollständig sein?
regular-languages
programming-languages
turing-completeness
sdleihssirhc
quelle
quelle
1*0
nachdenken , aber ich gehe davon aus, dass es sich um eine reguläre Sprache handelt.Antworten:
Kurz gesagt lautet die Antwort ja.
Aber Sie mischen zwei völlig unabhängige Bedeutungen des Begriffs "Sprache" (ja, das ist verwirrend):
Beachten Sie, dass Sie von "der C ++ - Sprache" aus zwei völlig unabhängigen Blickwinkeln sprechen können, wobei Sie die beiden unabhängigen Bedeutungen des Wortes "Sprache" verwenden:
Die Merkmale der "C ++ - Sprache" unter diesen beiden Gesichtspunkten hängen nicht zusammen.
Weitere Beispiele zum Trennen dieser Konzepte:
quelle
(([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)*
eine reguläre Sprache ist , die Grammatik einer Sprache der Klasse zu beschreiben , der Lage ist , 0Während der Satz von legalen Programmen in Jot regelmäßig ist, ist Jot selbst Turing-vollständig. Das bedeutet, dass jede berechenbare Funktion in Jot ausgedrückt werden kann. Wir können uns sogar eine Sprache einfallen lassen, in der alle binären Zeichenfolgen legal sind, aber die Sprache selbst ist vollständig (Übung). Sie sind Syntax und Semantik verwirrend.
Übrigens sind kontextfreie Sprachen (wahrscheinlich) auch nicht NP-vollständig, da sie über einen polynomiellen Zeitanalysealgorithmus verfügen.
quelle
Die Syntax allein (wie in Syntaxbäumen kodiert) moderner Programmiersprachen ist weit von allem entfernt, was sie tun. Tatsächlich sind die formalen Sprachen, die durch die Menge aller Programme in einer bestimmten Sprache definiert werden, die fehlerfrei kompiliert werden, selten sogar kontextfrei .
Statische und dynamische Semantik fließen in die Gleichung ein. Sie sind im Syntaxbaum unsichtbar, bestimmen jedoch, ob ein Codeteil tatsächlich ein Programm ist und was es berechnet. Unterm Strich ist die kontextfreie resp. reguläre formale Sprache, die durch "Syntax" definiert ist, ergibt eine Überapproximation der Programmiersprache.
Nun zur Beantwortung Ihrer Frage: Ja, das ist möglich. Denken Sie beispielsweise an eine Gödel-Nummerierung von Turing-Maschinen. Sie erhalten die "Programmiersprache" aller natürlichen Zahlen, die jeweils ein TM darstellen. Zugegeben, es ist keine schöne Sprache zum Programmieren, aber es ist sicherlich eine Turing-vollständige Sprache, die regelmäßig ist - sogar trivial.
quelle
Eine Programmiersprache ist Turing-vollständig, wenn sie aussagekräftig genug ist, um jede von Turing-Maschinen berechenbare Funktion anzugeben. Hier diskutieren wir die Macht der in den Programmiersprachen angegebenen Sprachen . ZB ist es nicht schwierig, einen Interpreter für Turing-Maschinen in Python zu schreiben, daher ist Python eine vollständige Programmiersprache für Turing.
Die Syntax einer Programmiersprache , dh die Menge von Zeichenfolgen, die gültigen Programmen in der Programmiersprache entsprechen, ist selbst eine Sprache. ZB die Menge aller möglichen Python-Programme berücksichtigen. Die Syntax einer Programmiersprache kann kontextsensitiv , kontextfrei , regulär usw. sein. Wir sind an der Schwierigkeit interessiert, zu überprüfen, ob ein bestimmter String ein gültiges Programm in der Programmiersprache ist (dies wird von Compilern / Interpreten durchgeführt). Wenn wir sagen, dass die Syntax einer Programmiersprache kontextfrei ist, bedeutet dies, dass es eine kontextfreie Grammatik für ihre Syntax gibt, und impliziert, dass es Push-Down-Automaten gibt, mit denen die Gültigkeit von Programmen überprüft werden kann.
Beachten Sie, dass die Einfachheit der Syntax einer Programmiersprache keine Einschränkung der Rechenleistung der in diesen Programmiersprachen angegebenen Programme bedeutet.
quelle
Die Antwort ist ja. Sie sehen, wie die akzeptierte Antwort besagt, dass eine Grammatik unabhängig von ihrer Bedeutung ist. In Chomskys eigenen Worten:
Wenn eine Grammatik genügend Sätze erzeugt, um alle Dinge zu beschreiben, die berechnet werden können, können wir ihren Sätzen willkürlich eine rechnerische Bedeutung zuweisen - eine für jedes Ding, das berechnet werden kann.
Als konkretes Beispiel hat die populäre Sprache
whitespace
eine reguläre Grammatik und vielleicht sogarx86 assembly languages
(muss überprüft werden).quelle