Pertanyaan tentang properti dari kelas bahasa reguler dan bahasa individual.
Ada banyak metode untuk membuktikan bahwa suatu bahasa tidak teratur , tetapi apa yang harus saya lakukan untuk membuktikan bahwa beberapa bahasa itu teratur? Misalnya, jika saya diberi tahu bahwa adalah biasa, bagaimana saya bisa membuktikan bahwa berikut ini juga teratur?L
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...
Saya membaca tentang Iota dan Jot dan menemukan bagian ini membingungkan: Tidak seperti Iota, di mana pohon sintaksis untuk string dapat bercabang baik di kiri atau di kanan, sintaks Jot secara seragam bercabang kiri. Akibatnya, Iota benar-benar bebas konteks, tetapi Jot adalah bahasa...
Saya baru saja menyelesaikan bab pertama dari Pengantar Teori Komputasi oleh Michael Sipser yang menjelaskan dasar-dasar automata terbatas. Dia mendefinisikan bahasa reguler sebagai apa pun yang dapat dijelaskan oleh automata terbatas. Tetapi saya tidak dapat menemukan di mana dia menjelaskan...
Untuk bahasa biasa L.L.L, misalkan menjadi jumlah kata dalam dengan panjang . Menggunakan bentuk kanonik Jordan (diterapkan pada matriks transisi yang tidak terotomatisasi dari beberapa DFA untuk ), orang dapat menunjukkan bahwa untuk , di mana adalah polinomial yang kompleks dan adalah "nilai...
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...
Kita tahu bahwa DFA setara dengan NFA dalam kekuatan ekspresif; ada juga algoritma yang dikenal untuk mengubah NFA menjadi DFA (sayangnya saya sekarang tahu penemu algoritma itu), yang dalam kasus terburuk memberi kita status , jika NFA kami memiliki status S2S2S2^SSSS Pertanyaan saya adalah: apa...
Wikipedia memiliki definisi berikut tentang lemma pemompaan untuk bahasa biasa ... Biarkan menjadi bahasa biasa. Kemudian ada bilangan bulat ≥ 1 hanya bergantung pada sehingga setiap string dalam panjang setidaknya ( disebut "panjang pemompaan") dapat ditulis sebagai = (yaitu, dapat dibagi...
Membiarkan L={an∣∃p≥n p, p+2 are prime}.L.={Sebuahn∣∃hal≥n hal, hal+2 adalah prima}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Apakah teratur?LL.L Pertanyaan ini tampak mencurigakan pada pandangan pertama dan saya menyadari bahwa itu terkait dengan dugaan kembar...
Saya terjebak pada pertanyaan berikut: "Bahasa reguler adalah persis yang diterima oleh automata terbatas. Mengingat fakta ini, menunjukkan bahwa jika bahasa LLL diterima oleh beberapa otomat terbatas, maka LRLRL^{R} juga diterima oleh beberapa yang terbatas; LRLRL^{R} terdiri dari semua kata LLL...
Saya mencoba menggunakan pemompaan lemma untuk membuktikan bahwa tidak teratur.L={(01)m2m∣m≥0}L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Inilah yang saya miliki sejauh ini: Asumsikan teratur dan biarkan p menjadi panjang pemompaan, jadi w = ( 01 ) p 2 p . Pertimbangkan setiap dekomposisi...
Pengaturan: ekspresi reguler dengan referensi kembali bahasa unary (alfabet 1 simbol) Apakah masalah berikut ini dapat ditentukan dalam pengaturan ini: Diberi ekspresi reguler dengan referensi, apakah itu mendefinisikan bahasa biasa? Misalnya, (aa+)\1mendefinisikan bahasa reguler, sementara...
Ada banyak (dan maksud saya banyak) bahasa yang dapat dihitung yang dapat didekati oleh Turing. Bisakah bahasa yang tak terhitung dapat menjadi pilihan
Menurut Wikipedia , untuk bahasa reguler ada konstanta dan polinomial sedemikian rupa sehingga untuk setiap angka kata-kata panjang n dalam L memenuhi
Saya tidak jelas tentang penggunaan frasa "tak terbatas" bahasa atau "terbatas" bahasa dalam teori komputer. Saya pikir akar masalahnya adalah bahwa bahasa seperti tidak terbatas dalam arti bahwa ia dapat menghasilkan jumlah string yang tak terbatas (tetapi dapat dihitung). Namun, itu masih dapat...
Perpotongan bahasa bebas konteks L dengan bahasa reguler M, dikatakan selalu bebas konteks. Saya memahami bukti konstruksi produk silang, tetapi saya masih belum mengerti mengapa ini bebas konteks tapi tidak teratur. Bahasa yang dihasilkan oleh persimpangan semacam itu memiliki string yang...
Perhatikan bahwa ini adalah pertanyaan yang terkait dengan belajar di kursus CS di universitas, BUKAN pekerjaan rumah dan dapat ditemukan di sini di bawah ujian Musim Gugur 20112. Inilah dua pertanyaan yang saya lihat dari ujian sebelumnya. Mereka tampaknya terkait, yang pertama: Membiarkan...
Diberikan bahasa dan , katakanlah bahwa gabungan tidak ambigu jika untuk semua kata , ada tepat satu dekomposisi dengan dan , dan ambigu sebaliknya. (Saya tidak tahu apakah ada istilah yang mapan untuk properti ini — hal yang sulit untuk dicari!) Sebagai contoh sepele, gabungan dari dengan dirinya...
Jika saya memiliki Tata Bahasa Tipe 3, itu dapat direpresentasikan pada otomat pushdown (tanpa melakukan operasi apa pun pada stack) sehingga saya dapat mewakili ekspresi reguler dengan menggunakan bahasa bebas konteks. Tapi bisakah saya tahu jika tata bahasa tipe 3 adalah , L L ( 1 ) , S L R ( 1 )...
Apakah ada karakterisasi aljabar dari jumlah kata dengan panjang tertentu dalam bahasa biasa? Wikipedia menyatakan hasil yang agak tidak tepat: Untuk bahasa biasa ada konstanta λ 1 ,LLL dan polinomial p 1 ( x ) ,λ1,…,λkλ1,…,λk\lambda_1,\,\ldots,\,\lambda_k sedemikian rupa sehingga untuk...