Bisakah bahasa formal digunakan untuk mempelajari notasi matematika?

Pertanyaan: Apakah ada teks pengantar dalam bahasa formal atau teori bahasa pemrograman yang membahas bagaimana menerapkannya pada studi notasi optimal?

Secara khusus, saya tertarik untuk mempelajari apa bahasa stack, pohon parse, dan indeks, dan bagaimana memprediksi kapan suatu jenis notasi tertentu akan mengarah pada redundansi eksponensial.

Saya pada dasarnya tidak memiliki latar belakang baik dalam bahasa formal / tata bahasa atau teori pemrograman, karena sebagai mata pelajaran matematika satu-satunya ilmu komputer yang saya pelajari adalah algoritma dan teori grafik, serta sedikit sekali teori kompleksitas dan fungsi Boolean. Jadi, jika satu-satunya buku yang membahas ini bukan pengantar, saya akan berterima kasih atas jawaban bahwa kedua daftar buku-buku tersebut membahas ledakan notasi eksponensial serta buku pengantar yang akan mempersiapkan buku-buku yang langsung menjawab pertanyaan saya.

Konteks: Pertanyaan ini terinspirasi terutama oleh jawaban pada Physics.SE , yang mengatakan bahwa:

Sangat mudah untuk membuktikan (secara ketat) bahwa tidak ada notasi tanda kurung yang mereproduksi kontraksi indeks tensor, karena tanda kurung diuraikan oleh bahasa stack (tata bahasa bebas konteks dalam klasifikasi Chomsky) sementara indeks tidak dapat diuraikan dengan cara ini, karena mereka termasuk umum grafik. Tanda kurung menghasilkan pohon parse, dan Anda selalu memiliki banyak pohon maksimal secara eksponensial di dalam grafik apa pun, sehingga ada redundansi eksponensial dalam notasi.

Sepanjang sisa jawaban, contoh-contoh lain dari "ledakan notasi eksponensial" dibahas, misalnya dengan Petri Nets dalam biologi komputasi.

Ada juga contoh lain di mana notasi matematika sulit diurai, misalnya seperti yang disebutkan di sini ketika fungsi dan fungsi yang diterapkan pada argumen tidak dibedakan dengan jelas. Ini bisa menjadi sangat membingungkan ketika fungsi menjadi argumen dan argumen menjadi fungsi, misalnya di sini .

1. Teori bahasa formal tidak berkaitan dengan semantik bahasa. Itu mungkin tampak aneh, karena kita cenderung menganggap bahasa sebagai mekanisme untuk mengkomunikasikan sesuatu, tetapi jika Anda memikirkannya, sebenarnya ada dua tingkat pemahaman bahasa (setidaknya): tingkat permukaan, di mana bahasa adalah aliran leksem, dan tingkat denotasional yang mendasarinya yang lebih atau kurang bercerai dari representasi permukaan. (Chomsky mengemukakan tingkat "transformasional" menengah untuk mengatasi beberapa batasan dengan CFG tetapi itu tidak relevan di sini.) Akibatnya, dimungkinkan untuk mengatakan "hal yang sama" dalam bahasa yang berbeda; Chomsky bukan Whorfian. (Lihat Wikipedia untuk ikhtisar singkat, dengan beberapa referensi).

2. Meskipun demikian, tata bahasa bebas konteks tidak cukup untuk membedakan ucapan yang benar dan yang salah. Chomsky memberikan contoh klasik: Gagasan yang tidak berwarna tertidur nyenyak (yang salah dieja, sebagai orang AS). Lihat Wikipedia , lagi. (Sayangnya Wikipedia tidak memiliki versi Bahasa Inggris Kanada.) Pembagian yang tepat antara kesalahan sintaksis dan semantik sulit, jika bukan tidak mungkin, untuk demarkasi dan telah ada perdebatan besar tentang topik ini di bidang CS, yang saya tidak akan bahkan berusaha untuk berdiskusi di sini karena saya selalu mendapat masalah ketika saya melakukannya. Namun, kita dapat mengidentifikasi satu aturan tata bahasa klasik yang ada dalam banyak bahasa manusia: perjanjian kata benda / kata kerja. Saya tidak setujuSepertinya saya menjadi kesalahan sintaksis dalam arti bahwa saya memahami maksud ucapan dengan sempurna tetapi juga mengenalinya sebagai kesalahan. Tetapi masalah sintaksis ini hanya dapat ditangkap oleh tata bahasa bebas konteks jika kita menyebutkan semua perjanjian yang mungkin. Artinya, kita bisa menulis sesuatu yang samar-samar suka$S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, tetapi mudah untuk melihat bagaimana pencacahan bisa keluar dari tangan dalam bahasa dengan aturan perjanjian yang lebih rumit (gender, misalnya).

3. Masalah dengan tata bahasa bebas konteks adalah bahwa mereka bebas konteks, meskipun Anda tidak harus menganggap deskripsi itu terlalu serius karena mudah untuk jatuh ke dalam perangkap salah menafsirkan penggunaan teknis dari kata-kata umum (yang, menurut saya, adalah dasar pertanyaan ini di tempat pertama). Itu berarti bahwa nonterminal (suka$NP$di atas) harus mendapatkan set frasa yang persis sama terlepas dari konteks di mana ia muncul. Jadi kita tidak bisa menulis, misalnya,$S \to NP_X VP_X$ dengan pengertian itu $X$perlu diisi dengan cara yang sama di kedua ekspansi. (Ini adalah salah satu masalah yang berusaha diatasi oleh tata bahasa transformasional.)

4. Itulah masalah dengan kontraksi indeks tensor. Kontraksi indeks tensor menempatkan persyaratan tertentu pada penggunaan variabel indeks: variabel indeks harus digunakan tepat dua kali, dalam hal ini tidak dapat berada di sisi kiri, atau tepat sekali, di mana ia harus di sebelah kiri. sisi tangan. (Karena saya bukan seorang ahli fisika, saya akan tergoda untuk menciutkan hal itu dengan mengatakan bahwa suatu variabel indeks harus muncul tepat dua kali secara keseluruhan. Tetapi ada perbedaan semantik antara variabel bebas dan tempat penampung, yang penting bagi pemahaman tentang ekspresi.) Di sini, tidak ada koleksi terbatas variabel indeks sederhana dan tidak ada batasan jumlah placeholder yang digunakan. Selain itu, mengganti nama placeholder tidak mempengaruhi semantik asalkan nama-nama baru tidak digunakan di tempat lain dalam ekspresi,

5. Faktanya adalah mungkin untuk secara tegas membuktikan pernyataan bahwa tata bahasa bebas konteks tidak dapat menangkap kesepakatan kontekstual, seperti dalam contoh sebelumnya. Saya pikir itu ada hubungannya dengan apa yang dinyatakan klaim yang dikutip. Bergantung pada seberapa sombongnya Anda, Anda mungkin menemukan itu menarik untuk belajar lebih banyak, tetapi saya tidak berpikir itu akan menjadi sangat relevan dengan wawasan filosofis atau fisik yang Anda cari.

6. Artikel-artikel terkait lainnya, tentang bentuk permukaan yang tidak menguntungkan dalam notasi matematika, hanyalah anekdotal; tak satu pun dari mereka, sejauh yang saya bisa lihat, membuat titik yang dalam atau bahkan dangkal yang relevan dengan teori bahasa formal, sama seperti lelucon yang mungkin terkenal bahwa ikan satu orang adalah ikan poisson orang lain bahkan tidak samar-samar wawasan tentang linguistik romansa, tetapi masih lucu (IMO).