Kontinuierliche Mathematik und formale Sprachtheorie

9

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.

Rustam
quelle
1
Für mich ist das beste Beispiel das wunderbare Papier von Flajolet: Flajolet, P. (1987). Analytische Modelle und Mehrdeutigkeit kontextfreier Sprachen. Theoretical Computer Science, 49 (2-3), 283-309. Die meisten Arbeiten von Flajolet befassen sich mit der Verbindung zwischen (komplexer) Analyse, formalen Sprachen und Kombinatorik. Weitere Beispiele finden Sie in seinem Buch mit Sedgewick.
Lamine
1
@Lamine Bitte überlegen Sie, Ihren Kommentar in eine Antwort umzuwandeln.
Hermann Gruber

Antworten:

6

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:

Die ersten beiden der obigen Referenzen geben auch einen Überblick über den mathematischen und / oder historischen Hintergrund.

Hermann Gruber
quelle
5

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 .

Lamine
quelle
2

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

gsv
quelle
Ich denke nicht, dass es die Frage beantwortet. Das verlinkte Papier handelt von einem algebraischen Problem. Ich sehe dort keinen interessanten Zusammenhang mit der Analyse.
Sasho Nikolov