Was wird aus kontextsensitiven Grammatiken, wenn $ \ epsilon $ productions zulässig sind?

Question

Die ursprüngliche Formulierung der 3 eingeschränkten Grammatikarten von Chomsky umfasste alle die Einschränkung, dass die rechte Seite eines Ersatzes nicht $ \ epsilon $ (nichtvertraglich).Dies kann jedoch (und ist in der Regel) für regelmäßige und kontextfreie Grammatiken aufgehoben (dh sie dürfen Produktionen des Formulars $ X \ to \ Epsilon $ ), ohne die Klasse der erzeugten Sprachen zu ändern.

Die Regel bleibt jedoch nach kontextsensitiven Grammatiken.

Meine Frage ist gegeben, da eine Grammatik mit Produktionen $ \ alpha x \ beta \ to \ alpha \ xi \ beta $ where $ \ alpha, \ beta, \ xi \ in (n \ cup t) ^ * $ (dh eine kontextsensitive Grammatik mit $ \ Epsilon $ -Rules), welche Klasse von Sprachen beschreibt das?Die rekursiv geneignern (gleiche wie uneingeschränkte Grammatiken) oder etwas anderes?

Answer 1

Es kann angezeigt werden, dass die kontextsensitiven Grammatiken, die Sie beschreiben, gleichwertig sind, um nur nach Produktionen zu fragen $ \ alpha \ bis \ beta $ mit $ \ labt \ alpha \ rutz \ le \ lvert \ betweder \ rutzet $ .So lässt Productions $ a \ to \ vareepsilon $ nur die Einschränkung der Längen entfernt, und Sie haben auf uneingeschränkten Grammatiken gelandet.