Wo liegen die Grenzen der Kontrolle in der formalen Sprachtheorie? Dieser Artikel untersucht die Feinheiten der linksseitigsten Ableitung in Matrixgrammatiken, einem klassischen Thema des regulierten Umschreibens. Während Matrixgrammatiken seit Jahrzehnten untersucht werden, untersucht diese Forschung systematisch verschiedene Möglichkeiten zur Definition der linksseitigsten Ableitung. Zwölf Arten einer solchen Einschränkung werden definiert, von denen nur vier in der Literatur diskutiert werden. Für sieben von ihnen finden wir einen Beweis für eine Charakterisierung rekursiv aufzählbarer Sprachen (durch Matrixgrammatiken mit beliebigen kontextfreien Regeln, aber ohne Erscheinungsprüfung). Drei weitere Fälle charakterisieren die rekursiv aufzählbaren Sprachen modulo einem Morphismus und einer Schnittmenge mit einer regulären Sprache. Letztendlich löst diese Studie fast alle Probleme, die auf Seite 67 der Monographie [7] als offen aufgeführt sind, und bringt das Feld erheblich voran. Darüber hinaus wird eine Charakterisierung rekursiv aufzählbarer Sprachen für Matrixgrammatiken mit der linksseitigsten Einschränkung gefunden, die auf Klassen einer gegebenen Partition des Nichtterminalalphabets definiert ist.
Dieser Artikel passt zum Fokus des International Journal of Foundations of Computer Science auf die theoretische Informatik. Durch die systematische Untersuchung der linksseitigsten Ableitung in Matrixgrammatiken und die Charakterisierung rekursiv aufzählbarer Sprachen trägt der Artikel zum Umfang der Zeitschrift bei. Die Ergebnisse zu Einschränkungen und Klassifikationen in der formalen Sprachtheorie sind für die Leserschaft der Zeitschrift relevant.