Matematika berkelanjutan dan teori bahasa formal

9

Apakah ada beberapa hasil pada penyelesaian masalah bahasa formal menggunakan analisis matematika, matematika kontinu.

Misalnya, menyelesaikan masalah non-kekosongan persimpangan untuk bahasa bebas konteks dan bahasa biasa.

fl.formal-languages automata-theory context-free Rustam
sumber
1
Bagi saya contoh terbaik adalah kertas indah oleh Flajolet: Flajolet, P. (1987). Model analitik dan ambiguitas bahasa bebas konteks. Ilmu Komputer Teoritis, 49 (2-3), 283-309. Sebagian besar karya Flajolet adalah tentang hubungan antara analisis (kompleks), bahasa formal dan kombinatorik. Anda dapat menemukan lebih banyak contoh dalam bukunya dengan Sedgewick.
Lamine
1
@Lamine tolong pertimbangkan mengubah komentar Anda menjadi jawaban.
Hermann Gruber

Jawaban:

6

Lamine mengomentari kaitannya dengan teorema enumerasi Chomsky-Schützenberger . Baru-baru ini, beberapa masalah penelitian dalam teori bahasa formal diselesaikan menggunakan matematika kontinu melalui koneksi ini. Sebagai contoh:

Dua referensi pertama di atas juga memberikan survei tentang latar belakang matematika dan / atau sejarah.

Hermann Gruber
sumber
5

Salah satu koneksi pertama adalah melalui fungsi pembangkit. The Chomsky-Schutzenberger teorema menyatakan bahwa fungsi pembangkit dari jumlah kata dari CFL ambigu adalah aljabar. Dalam makalahnya, Flajolet membuktikan bahwa beberapa CFL secara inheren ambigu dengan menunjukkan bahwa fungsi pembangkitnya bersifat transendental ("perilaku lokal" mereka di sekitar singularitas mereka adalah karakteristik fungsi transendental, misalnya, istilah logaritmik muncul dalam ekspansi).

Secara umum, Anda harus melihat pada Combinatorics Analytic . Ini memberikan hubungan yang indah antara struktur formal dan analisis kompleks.

Flajolet, Philippe , model Analitik dan ambiguitas bahasa bebas konteks , Theor. Komputasi. Sci. 49, 283-309 (1987). ZBL0612.68069 .

Lamin
sumber
2

Karya Konstantin V. Safonov mungkin menarik. Misalnya "Pada Solvabilitas Sistem Persamaan Polinom Simbolik" .

Sistem persamaan polinomial non-komutatif yang dibahas dalam karya ini dapat diperlakukan sebagai tata bahasa yang menghasilkan bahasa formal. Misalnya, bahasa bebas konteks. Hubungan ini dibahas dalam Pendahuluan.

Ada lebih banyak karya Konstantin V. Safonov tentang topik ini, dan beberapa di antaranya lebih dekat dengan teori bahasa formal, tetapi mereka dalam bahasa Rusia. Misalnya AN REPRESENTASI INTEGRAL POLINOMI SINTETIS .

Daftar lengkap publikasi yang dapat Anda temukan di sini: http://www.mathnet.ru/rus/person37125

gsv
sumber
Saya tidak berpikir itu menjawab pertanyaan. Makalah terkait adalah tentang masalah aljabar. Saya tidak melihat hubungan yang menarik dengan analisis di sana.
Sasho Nikolov