Bahasa reguler planar

33

Di kelas saya seorang siswa bertanya apakah semua automata terbatas dapat digambar tanpa melewati batas (sepertinya semua contoh saya lakukan). Tentu saja jawabannya negatif, otomat yang jelas untuk bahasa memiliki struktur , grafik lengkap pada lima node . Yuval telah menunjukkan struktur yang serupa untuk bahasa terkait.{x∈{a,b}∗∣#a(x)+2#b(x)≡0mod5}K5

Pertanyaan saya adalah sebagai berikut: bagaimana kita menunjukkan bahwa setiap otomat keadaan terbatas untuk bahasa ini adalah non-planar? Dengan karakterisasi Myhill-Nerode seperti itu mungkin dapat ditetapkan bahwa struktur bahasa hadir dalam diagram, tetapi bagaimana kita membuat ini tepat?

Dan jika itu bisa dilakukan, apakah ada karakterisasi "bahasa reguler planar"?

regular-languages finite-automata planar-graphs Hendrik Jan
sumber
Juga, masalah memutuskan apakah bahasa reguler dapat dikenali oleh DFA planar tampaknya sulit. Desidabilitasnya terbuka, dan memiliki kaitan dengan masalah terbuka dalam teori grafik.
Denis

Jawaban:

30

Tidak benar bahwa setiap DFA untuk bahasa ini adalah non-planar:

Contoh tandingan

Berikut adalah bahasa yang benar-benar non-planar: Ambil FSA planar apa pun untuk bahasa ini. Jika kami menghapus semua status yang tidak terjangkau, kami masih mendapatkan grafik planar. Setiap negara yang dapat dijangkau memiliki enam tepi keluar yang berbeda , yang bertentangan dengan fakta yang diketahui bahwa setiap grafik planar memiliki paling banyak lima derajat.

{x∈{σ1,…,σ6}∗|∑i=16i#σi(x)≡0(mod7)}.

Yuval Filmus
sumber
22

Konsep tersebut telah diteliti sebelumnya. (Setelah Anda tahu jawabannya, google untuk itu ...)

Pertama ada karya lama oleh Book dan Chandra, dengan abstrak berikut.

Ringkasan. Ditunjukkan bahwa untuk setiap otomat kondisi-terbatas terdapat otomat nondeterministik ekivalen dengan grafik keadaan planar. Namun ada automata keadaan-terbatas tanpa otomat deterministik setara dengan grafik keadaan planar.

Contoh dan argumentasi yang diberikan adalah persis oleh Yuval dalam jawabannya!

Selain itu mereka juga mempertimbangkan alfabet biner.

Ada 35-state secara inheren nonplanar otomat deterministik atas alfabet 2 huruf.

Pekerjaan ini diteruskan agak baru-baru ini oleh Bonfante dan Deloup. Mereka menganggap embeddings topologi. Secara informal genus grafik adalah jumlah lubang yang harus ditambahkan untuk menanamkan grafik suatu permukaan tanpa melewati tepi. Grafik dengan genus nol adalah planar. Maka genus suatu bahasa adalah genus minimal automata untuk bahasa tersebut.

Teorema 9 (Hierarki Berbasis Genus). Ada bahasa reguler dari genus besar yang sewenang-wenang.

Pada bagian "State-minimal automata versus genus-minimal automata" orang menemukan hasilnya, buktinya adalah contoh pertama yang diberikan oleh Yuval (sepuluh negara bagian untuk membuat bahasa planar lima negara K5).

Proposisi 7. Terdapat automata deterministik dengan genus yang lebih rendah dari gen automaton minimalnya.

G. Confetti, F.Deloup: Genus bahasa reguler, Struktur Matematika dalam Ilmu Komputer, 2018. doi 10.1017 / S0960129516000037 . Juga ArXiv 1301.4981 (2013)

RV Book, AK Chandra, Inherently Nonplanar Automata, Acta informatica 6 (1976) doi 10.1007 / BF00263745

Hendrik Jan
sumber