Saat ini saya sedang membaca buku Pengantar Teori Komputasi (edisi ke-2 atau ke-3) oleh Michael Sipser , dan telah menemukan pertanyaan di Bab 1 - Bahasa Reguler , yaitu ketika penulis menyajikan ide bukti Teorema 1.49 - "Kelas bahasa reguler ditutup di bawah operasi bintang." menggunakan NFA.
Pendekatan yang disarankan adalah jika kita memiliki bahasa yang teratur dan ingin membuktikan itu juga biasa, kita bisa mengambil NFA dan memodifikasinya menjadi seperti pada gambar di bawah ini, yang kemudian mengenali NFA tertentu .
Dia mencatat:
Satu (sedikit buruk) ide adalah hanya menambahkan status awal ke set status terima. Pendekatan ini tentu saja menambah ke bahasa yang dikenali, tetapi juga dapat menambahkan string lain yang tidak diinginkan.
Saya telah menggambar NFA "buruk" seperti di bawah ini dan mencoba mencari tahu mengapa ini akan menghasilkan string yang tidak diinginkan. Namun, saya tidak dapat menemukan contoh kapan string yang tidak diinginkan dikenali. Mengapa gagasan ini menghasilkan NFA mengenali string yang tidak diinginkan?
Bisakah seseorang menunjukkan ini untuk saya atau memberi saya petunjuk, atau apakah saya salah mengerti penulis? Terima kasih sebelumnya!
sumber