Ob es einige Ergebnisse zur Lösung formaler Sprachprobleme mit mathematischer Analyse oder kontinuierlicher Mathematik gibt?
Zum Beispiel das Lösen des Problems der Nichtleere der Kreuzung für eine kontextfreie Sprache und eine reguläre Sprache.
9
Antworten:
Lamine kommentierte den Zusammenhang mit dem Chomsky-Schützenberger-Aufzählungssatz . Kürzlich wurden über diesen Zusammenhang einige Forschungsprobleme in der formalen Sprachtheorie mittels kontinuierlicher Mathematik gelöst. Beispielsweise:
Hermann Gruber, Jonathan Lee und Jeffrey Shallit. Aufzählung regulärer Ausdrücke und ihrer Sprachen . online verfügbar unter arxiv.org als arXiv: 1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira und Rogério Reis: Per Anhalter durch die analytische Kombinatorik . Theor. Comput. Sci. 528: 85 & ndash; 100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira und Rogério Reis: Durchschnittliche Größe von Automatenkonstruktionen aus regulären Ausdrücken . Bulletin des EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira und Rogério Reis: Zur durchschnittlichen Komplexität partieller Ableitungsautomaten für semi-erweiterte Ausdrücke . Journal of Automata, Languages and Combinatorics 22 (1-3): 5-28 (2017)
Die ersten beiden der obigen Referenzen geben auch einen Überblick über den mathematischen und / oder historischen Hintergrund.
quelle
Eine der ersten Verbindungen erfolgt über Generierungsfunktionen. Das Chomsky-Schützenberger- Theorem besagt, dass die Erzeugungsfunktion der Anzahl von Wörtern einer eindeutigen CFL algebraisch ist. In seiner Arbeit beweist Flajolet, dass mehrere CFL von Natur aus mehrdeutig sind, indem er zeigt, dass ihre Erzeugungsfunktion transzendent ist (ihr „lokales Verhalten“ um ihre Singularitäten ist charakteristisch für transzendentale Funktionen, zum Beispiel erscheinen logarithmische Begriffe in der Erweiterung).
Im Allgemeinen sollten Sie sich die analytische Kombinatorik ansehen . Es gibt eine schöne Verbindung zwischen formalen Strukturen und komplexer Analyse.
Flajolet, Philippe , Analytische Modelle und Mehrdeutigkeit kontextfreier Sprachen , Theor. Comput. Sci. 49, 283 & ndash; 309 (1987). ZBL0612.68069 .
quelle
Werke von Konstantin V. Safonov mögen interessant sein. Zum Beispiel "Zur Lösbarkeit von Systemen symbolischer Polynomgleichungen" .
Systeme nichtkommutativer Polynomgleichungen, die in dieser Arbeit diskutiert werden, können als Grammatiken behandelt werden, die formale Sprachen erzeugen. Zum Beispiel kontextfreie Sprachen. Diese Beziehung wird in der Einleitung erörtert.
Es gibt mehr Werke von Konstantin V. Safonov zu diesem Thema, und einige von ihnen sind eher der Theorie der formalen Sprachen verschlossen, aber sie sind auf Russisch. Zum Beispiel EINE INTEGRALE DARSTELLUNG DES SYNTAKTISCHEN POLYNOMS .
Eine vollständige Liste der Veröffentlichungen finden Sie hier: http://www.mathnet.ru/rus/person37125
quelle