TEORI KOMPUTASI DAN IMPLEMENTASINYA
1. Pengertian Teori Komputasi Teori komputasi (theory of computation) adalah cabang ilmu komputer teoritis (theoritical computer science). Cabang ilmu ini membahas apakah suatu masalah dapat dianalisis dan dipecahkan pada model komputasi menggunakan algoritma. 2. Teori komputasi dibagi menjadi 3 Teori otomata Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. Teori komputabilitas Teori komputabilitas bertujuan untuk memeriksa apakah persoalan komputasi dapat dipecahkan pada suatu model komputasi teoritis. Dengan kata lain, teori komputabilitas mengklasifikasikan persoalan sebagai dapat dipecahkan (solvable) atau persoalan yang tidak dapat dipecahkan (unsolvable). Teori kompleksitas