Key points are not available for this paper at this time.
Wir schlagen ein skalierbares Rahmenwerk zur Entscheidung, Beweisführung und Erklärung der (Un-)Äquivalenz von kontextfreien Grammatiken vor. Wir präsentieren eine Implementierung des Rahmenwerks und bewerten es anhand großer Datensätze, die innerhalb von Bildungssystemen gesammelt wurden. Obwohl das Äquivalenzproblem für kontextfreie Sprachen im Allgemeinen unentscheidbar ist, kann das Rahmenwerk einen großen Teil dieser Datensätze bearbeiten. Es führt Techniken aus mehreren Bereichen ein und kombiniert diese, wie eine abstrakte Grammatiktransformation Sprache, um äquivalente Grammatiken sowie ausreichend ähnliche nicht-äquivalente Grammatiken zu identifizieren, theoriebasierte Vergleichsalgorithmen für eine große Klasse von kontextfreien Sprachen und eine von der Graphentheorie inspirierte Grammatikkanonisierung, die es ermöglicht, isomorphe Grammatiken effizient zu identifizieren.
Schmellenkamp et al. (Thu,) haben diese Frage untersucht.