Finite State Machine, Keterbagian, Basis, dan Perbedaan Kesulitan

Saya terpikirkan sebuah permasalahan sebagai berikut saat merancang PR untuk kuliah Teori Bahasa dan Automata.

Misalkan k merupakan bilangan asli. Diberikan bahasa L_k \subseteq \{0,1\}^* yang berisi representasi biner dari bilangan-bilangan asli yang habis dibagi k. Apakah bahasa L reguler?

Jawabannya, setelah berpikir sedikit, adalah ya.

Padahal, secara kasat mata untuk k yang agak aneh, sepertinya representasi biner dari bilangan yang habis dibagi k terlihat acak. Misalnya saja k=7, maka string-string di L_7 adalah 0, 111, 1110, 10101, 11100, 100011, \dots.

Namun, jika kita tahu makna representasi biner dari L_7 sendiri, kita bisa membuat FSM-nya dengan mudah. FSM untuk L_7 adalah sebagai berikut:

div7Tidak sulit untuk merancang FSM ini jika kita cukup membayangkan kelas-kelas ekivalensinya terlebih dahulu yaitu sesuai “sisa pembagian bilangan yang diterima saat ini oleh 7“. Selanjutnya, jika menerima 0 berarti cukup untuk memindahkan ia dari kelas m \pmod{7} ke kelas 2m \pmod{7}. Demikian pula jika menerima 1 berarti cukup untuk memindahkan ia dari kelas m \pmod{7} ke kelas 2m+1 \pmod{7}. Strategi ini pun dapat diterapkan untuk k umum. Bahkan, hal ini juga berlaku untuk representasi dalam basis berapapun: basis 3, basis 8, basis 10, basis 16, basis 1000, dan lain-lain. Namun, soal ini konyol jika yang ditanyakan adalah dalam basis 1 yang FSM-nya sangat obvious, yaitu dibangun dari regex (1111111)^*.

Basis dan Perbedaan Kesulitan

Hal yang cukup mengganggu saya adalah jika kita memandang permasalahan lain yang berbau-bau teori bilangan. Apakah pada dasarnya permasalahan pengenalan sifat bilangan seperti ini tidak terlalu peduli dengan “basis”? Misalnya, ada suatu predikat logika P(n) (misalnya P(n): n merupakan bilangan prima) dengan domain n bilangan asli. Pandanghimpunan alfabet \Sigma_i yang berisi alfabet-alfabet yang dibutuhkan untuk membangun representasi basis i dari sembarang bilangan asli. Misalkan L_{P,i} \subseteq \Sigma_i^* sehingga L_{P,i} berisi representasi basis i untuk semua bilangan asli n di mana P(n) bernilai benar.

Pertanyaan yang mengusik adalah:

Diberikan suatu predikat P dan misalkan bahasa L_{P,k} \subseteq \Sigma_k^* merupakan bahasa reguler untuk suatu k. Apakah ini berarti L_{P,m} merupakan bahasa reguler untuk setiap m?

Jika melirik permasalahan keterbagian di atas, kita tahu bahwa P(n): n habis dibagi d, merupakan permasalahan yang tidak mengenal basis. Dengan kata lain, permasalahan keterbagian tidak peduli dengan representasi bilangan asli yang diterimanya. Namun, bagaimana dengan permasalahan lain? Apakah setiap bahasa benar-benar tidak peduli dengan alfabet-alfabet yang digunakannya? Atau, sebenarnya it matters?

Sayangnya, ada permasalahan yang sensitif dengan bahasa yang digunakannya. Contohnya adalah permasalahan berikut:

P_2(n): n merupakan dua berpangkat (n=2^k, k \ge 0).

Jika dipandang dalam basis dua, ini masalah yang obvious. Kita dapat dengan mudah membuat regex untuk L_{P_2,2}, yaitu 10^*. Namun, sebutlah dalam basis L_{P_2,1}, kita dapat menunjukkan bahwa bahasa \{a^{2^n}:n \ge 0\} merupakan bahasa yang tak reguler dengan Teorema Pumping.

Saya sendiri belum memikirkan apakah L_{P_2,k} reguler untuk k yang lain….

Cuman, ini merupakan masalah yang menurut saya menarik untuk dipelajari.

Pertama, diberikan predikat P, apakah ia sensitif terhadap basis? Jika ya, basis yang bagaimana ia menjadi reguler? Kedua, kelas predikat mana saja yang tidak sensitif terhadap basis? Bagaimana predikat-predikat ini saling terhubung?

Apakah yang bisa membantu saya mencari bacaan yang bisa membantu saya memahami masalah ini? Saya akan sangat senang jika ada yang bisa memberikan arahan.

 

 

 

Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s