Entscheidbare Sprachen und uneingeschränkte Grammatik?

Turingmaschinen und uneingeschränkte Grammatiken sind zwei verschiedene Formalismen, die die RE-Sprachen definieren. Einige RE-Sprachen sind entscheidbar, aber nicht alle.

Wir können die entscheidbaren Sprachen mit Turing-Maschinen definieren, indem wir sagen, dass eine Sprache entscheidbar ist, wenn es ein TM für die Sprache gibt, die alle Zeichenfolgen in der Sprache anhält und akzeptiert und alle Zeichenfolgen, die nicht in der Sprache enthalten sind, anhält und ablehnt. Meine Frage lautet: Gibt es eine analoge Definition von entscheidbaren Sprachen, die auf uneingeschränkten Grammatiken und nicht auf Turing-Maschinen basiert?

computability turing-machines formal-grammars templatetypedef
quelle

Antworten:

Eine Sprache ist entscheidbar, wenn sie halb entscheidbar ist und ihre Ergänzung halb entscheidbar ist. Darüber hinaus ist eine Sprache rekursiv aufzählbar, wenn sie halbentscheidbar ist und Sie somit eine uneingeschränkte Grammatik finden können. Deshalb:

$L$ $G$ $L(G) = L$ $\bar G$ $L(\bar G) = \bar L$

Simon S.
quelle

Sind nicht auch "halbentscheidbare" und "rekursiv aufzählbare" Synonyme?

Templatetypedef

1. IIRC Es gibt keine bekannte Klasse formaler Grammatiken, die entscheidbaren Sprachen entsprechen, daher denke ich nicht, dass dies mit einer einzigen uneingeschränkten Grammatik möglich ist. 2. Ja, sie bedeuten zufällig dasselbe.

Simon S

Sie irren sich über die Definition der Entscheidbarkeit. Entscheidbar bedeutet "es gibt eine Turingmaschine, die die Antwort berechnet". Die Beziehung, die Sie als Definition zitieren, ist tatsächlich ein Satz, den ich Emile Post zugeschrieben habe.

Andrej Bauer

Als nächstes sind Semidecidability und rekursive Aufzählbarkeit keine Synonyme, aber sie sind äquivalente Begriffe. Ein Satz ist halbentscheidbar, wenn es sich um den Stoppsatz einer Turing-Maschine handelt, während er rekursiv aufzählbar ist, wenn er von einer Turing-Maschine aufgezählt wird.

Andrej Bauer

1. Sie haben Recht, die Entscheidbarkeit ist nicht unbedingt so definiert (kann es aber sein), und deshalb habe ich die Antwort bearbeitet. 2. Deshalb habe ich geschrieben "sie bedeuten zufällig dasselbe", vielleicht ist "Synonym" das falsche Wort.

Simon S

$\mathrm{R}$

Jede nützliche Klasse von Grammatiken ist aufzählbar, und
$\mathrm{R}$

Das erste ist offensichtlich kein strenger Satz (und kann es auch nicht sein), es ist nur eine wertende Vermutung. Die Menge aller Grammatiken ist aufzählbar, und jede Einschränkung, die nicht entscheidbar ist, ist an sich wahrscheinlich nicht sehr nützlich¹; Insbesondere wird es keine syntaktische Einschränkung sein (wie bei Chomsky).

Das zweite ist formal wahr, siehe auch hier .

Natürlich haben die Leute solche Einschränkungen definiert , und diese Klassen haben ihre Verwendung, aber es ist sogar schwer zu erkennen, ob eine bestimmte Grammatik in einfachere Unterklassen fällt.

Raphael
quelle

Warum gilt dieses Argument nicht auch für Turing-Maschinen? Es gibt eine nützliche Klasse von TMs für R (die Entscheider), obwohl sie nicht aufzählbar sind.

Templatetypedef

@templatetypedef: Der Gedanke kam mir in den Sinn. 1) Der Satz von Turingmaschinen für R ist etwas "immateriell". Es ist wohl nur im theoretischsten Sinne "nützlich". 2) Das TM ist ein operatives Modell, während Grammatiken eher ein deklaratives (wenn generatives) Modell sind. Daher ist es unwahrscheinlich, dass sogar eine Eigenschaft existiert, die so "nutzlos" ist wie die von R-TMs. (Auch dies ist alles intuitives Geschwätz.)

Raphael

Diese Frage wird in einem Artikel von Henning Fernau aus dem Jahr 1994 behandelt. Henning stellt fest:

Als Beispiel betrachten wir die Familie der rekursiven Sprachen. Es ist eine offene Frage, ob es eine "natürliche" grammatikalische Charakterisierung dieses Sprachunterrichts gibt. Wie wir im Folgenden zeigen werden, muss jede Grammatikfamilie, die die rekursiven Sprachen charakterisiert, einige seltsame Eigenschaften haben.

Wir leiten den Leser, der neugierig auf diese seltsamen Eigenschaften ist, auf das Papier.

Yuval Filmus
quelle