Dengan hanya mempertimbangkan alfabet , string yang dapat diberikan sebagai input ke mesin Turing berasal dari himpunan Σ ∗ . Tetapi apakah masuk akal untuk input menjadi string biner yang tak terbatas? Sebagai contoh jika mesin Turing menerima semua string dimulai dengan 0, apakah string biner nol...
Pertanyaan ini dimigrasikan dari Stack Overflow karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . Saya membuat ekspresi reguler sederhana lexer dan parser untuk mengambil ekspresi reguler dan menghasilkan pohon parsenya. Membuat
Apakah konteks bahasa berikut ini gratis? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Seperti yang ditunjukkan oleh sdcvvc, sebuah kata dalam bahasa ini juga...
Apakah tugas perangkat lunak (sistem operasi) untuk mendeteksi stack overflow atau apakah stack overflow terdeteksi di perangkat keras, menyebabkan pengecualian pada
Saya telah mendengar beberapa kali bahwa untuk nilai n yang cukup kecil, O (n) dapat dipikirkan / diperlakukan seolah-olah itu O (1). Contoh : Motivasi untuk melakukannya didasarkan pada gagasan yang salah bahwa O (1) selalu lebih baik daripada O (lg n), selalu lebih baik daripada O (n). Urutan...
Ada banyak teknik untuk membuktikan bahwa bahasa adalah tidak bebas konteks, tapi bagaimana saya membuktikan bahwa bahasa adalah bebas konteks? Teknik apa yang ada untuk membuktikan ini? Jelas, salah satu caranya adalah dengan menunjukkan tata bahasa bebas konteks untuk bahasa tersebut. Apakah ada...
Sebagian besar dari kita tahu korespondensi antara logika kombinasi dan kalkulus lambda . Tapi saya belum pernah melihat (mungkin saya belum melihat cukup dalam) setara dengan "combinator yang diketik", sesuai dengan kalkulus lambda yang diketik sederhana. Apakah hal seperti itu ada? Di mana orang...
Pertanyaan ini dimigrasikan dari Theoretical Computer Science Stack Exchange karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . Diketahui bahwa setiap masalah optimasi / pencarian memiliki masalah keputusan yang setara. Misalnya
Pernyataan Masalah Informal: Diberikan string, mis. ACCABBABSEBUAHCCSEBUAHBBSEBUAHBACCABBAB , kami ingin mewarnai beberapa huruf merah dan beberapa huruf biru (dan beberapa tidak sama sekali), sehingga hanya membaca huruf merah dari kiri ke kanan menghasilkan hasil yang sama seperti membaca hanya...
Pertanyaan ini terinspirasi oleh komentar di StackOverflow . Selain mengetahui masalah NP-lengkap dari buku Garey Johnson, dan banyak lainnya; adakah aturan praktis untuk mengetahui apakah suatu masalah terlihat seperti masalah NP-complete? Saya tidak mencari sesuatu yang ketat, tetapi untuk...
Dengan anggapan permintaan cache l1 dan l2 menghasilkan kesalahan, apakah prosesor berhenti sampai memori utama telah diakses? Saya mendengar tentang gagasan untuk beralih ke utas lain, jika demikian, apa yang digunakan untuk membangunkan utas yang
Catatan, sementara saya tahu cara memprogram, saya cukup pemula dalam teori CS. Menurut jawaban ini Kelengkapan Turing adalah konsep abstrak dari kemampuan komputasi. Jika suatu bahasa Turing lengkap, maka ia mampu melakukan perhitungan apa pun yang bisa dilakukan bahasa lengkap Turing...
Saya telah melihat dua definisi pohon biner seimbang, yang terlihat berbeda bagi saya. Pohon biner seimbang jika untuk setiap node itu berpendapat bahwa jumlah node dalam di subtree kiri dan jumlah node dalam di subtree kanan berbeda paling banyak 1. Pohon biner seimbang jika untuk setiap dua...
Kapan beberapa (relatif) dasar (pikirkan siswa CS tingkat perguruan tinggi tahun pertama) ketika seseorang akan menggunakan rekursi alih-alih hanya satu lingkaran?
Saya tahu bahwa algoritma Euclid adalah algoritma terbaik untuk mendapatkan GCD (pembagi umum yang hebat) dari daftar bilangan bulat positif. Namun dalam praktiknya Anda dapat membuat kode algoritma ini dengan berbagai cara. (Dalam kasus saya, saya memutuskan untuk menggunakan Java, tetapi C / C ++...
Saya sedang mencari algoritma untuk mendistribusikan nilai dari daftar sehingga daftar yang dihasilkan sebagai "seimbang" atau "didistribusikan secara merata" sebanyak mungkin (dalam tanda kutip karena saya tidak yakin ini adalah cara terbaik untuk menggambarkannya ... nanti saya akan memberikan...
Saya mengalami kesulitan memahami bukti tentang keraguan atas Masalah yang Menghambat. Jika kembali apakah program yang perhentian pada input b , mengapa kita harus melewati kode P untuk kedua a dan b ?H(a,b)H(a,b)H(a,b)aaabbbPPPaaabbb Mengapa kita tidak bisa memberi makan dengan P dan beberapa...
Anda punya satu koin. Anda dapat membaliknya sebanyak yang Anda inginkan. Anda ingin menghasilkan bilangan acak rrr sehingga a≤r<ba≤r<ba \leq r < b mana .r,a,b∈Z+r,a,b∈Z+r,a,b\in \mathbb{Z}^+ Distribusi angka harus seragam. Mudah jika :b−a=2nb−a=2nb -a = 2^n r = a + binary2dec(flip n...
Salah satu hyperparameter untuk jaringan LSTM adalah suhu. Apa
Berikut dugaan untuk ekspresi reguler: Untuk ekspresi reguler , biarkan panjang | R | menjadi jumlah simbol di dalamnya, mengabaikan tanda kurung dan operator. Misalnya | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR|R||R||R||0∪1|=|(0∪1)∗|=2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*| = 2 Dugaan: Jika dan...