Fungsi Rasional dan CFL

8

Dalam pekerjaan saya muncul masalah klasifikasi CFL di bawah gambar fungsi rasional. Dalam istilah lain, apa kelas bahasa bahasa membentuk , untuk konteks tetap bahasa bebas L dan deterministik negara yang terbatas transduser T . Saya telah memperoleh beberapa hasil mudah seperti bahasa Dyck dengan dua kawat yang sesuai dengan CFL dan bahasa Dyck dengan satu penjepit adalah subset ketat dari CFL, sekarang ada beberapa masalah yang masih menarik bagi saya, tetapi saya tidak percaya bahwa tidak ada telah menemukannya. Apakah ada makalah tentang hal ini? Klasifikasi Googling dari CFL atau Fungsi Rasional (Deterministic FST) + CFL memberikan hasil yang buruk.T(L)LT

Alexander Rubtsov
sumber
2
Teorema Chomsky-Schützenberger akan jatuh dalam keluarga hasil ini. Orang-orang (yaitu Ginsburg dan lainnya) pindah dari sana ke gagasan Abstract Families of Languages ​​(AFL).
Sylvain

Jawaban:

3

M(L)

Hendrik Jan
sumber