Ilmu komputer memiliki dua komponen utama: pertama, model dan gagasan mendasar mengenai komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan rancangan dari teori. Teori bahasa dan otomata merupakan bagian pertama. Secara teoritis ilmu komputer diawali dari sejumlah disiplin ilmu, antara lain ahli biologi mempelajari neural network, insinyur elektro mengembangkan switch-ing sebagai tool untuk mendesain hadware, matematikawan bekerja mendasarkan logika, dan ahli bahasa menyelidiki tata bahasa untuk natural language.
Finite state aoutomata dan ekspresi regular awalnya dikembangkan berdasar pemikiran neural network dan switching circuit. Finiti state aoutomata merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter-karakter ke dalam token, yang berupa unit terkecil seperti nama, variabel, dan keyword. Dalam sistem penulisan kompilator secara otomatis akan mentransformasikan ekspresi regular ke dalam finiti state automata untuk dipakai sebagai penganalisis leksikal. Finite state automata dan ekspresi regular dipakai pula dalam text editor, pattern-matching, sejumlah pemrosesan teks, dan program file-searching, dan sebagai konsep matematis untuk aplikasi di disiplin lain seperti logika.
Suatu bahasa pemrograman harus didefinisikan secara tepat. Spesifikasi dari sebuah bahasa pemrograman meliput hal-hal berikut.
- Himpunan simbol-simbol (alphabet) yang bisa dipakai untuk membentuk program yang bener.
- Himpunan program yang bener secara sintaksis.
- Makna dari program tersebut.
Suatu teori hanya menarik bila itu membantu dalam mencari solusi terbaik. Tanpa penerapan, timbul pertanyaan "mengapa mempelajari teori" Teori memberikan konsep dan prinsip yang menolong untuk memahami 'perilaku' dari suatu disiplin ilmu. Bidang ilmu komputer meliput topik yang luas, dari perancangan mesin sampai pemrograman. Disamping perbedaan yang ada, terdapat prinsip-prinsip yang umum dipakai. Untuk mempelajari prinsip-prinsip dasar inilah kita mengkonstruksikan model abstrak dari komputer dan komputasi. Model ini memiliki fungsi-fungsi yang penting dan umum pada perangkat keras maupun perangkat lunak. Meskipun model tersebut terlalu sederhana untuk diterapkan langsung pada dunia nyata, keuntungan dari mempelajarinya adalah memberikan landasan, yang mana suatu pengembang didasarkan. Pendekatan dengan model ini tidak hanya dilakukan pada ilmu komputer, tetapi juga pada ilmu sains lainnya. Beberapa gagasan yang diutarakan memiliki penerapan yang penting. Misalnya, pada perancangan digital, bahasa pemrograman, dan kompilator.
KONSEP BAHASA DAN OTOMATA
Sebuah simbol adalah suatu entitas abstrak yang tidak kita definisikan secara formal, seperti halnya kita tidak mendifinisikan titik dan garis pada geometri. Huruf dan digit adalah contoh dari simbol yang sering dipakai. Sebuah string (kata/untai) adalah suatu deretan berhingga dari simbol-simbol. Sebagai contoh, 'a' , 'b', 'c' adalah simbol-simbol, dan 'abcb'adalah suatu string. Panjang string disini adalah jumlah simbol yang membentuk string tersebut contoh:
'abad' panjangnya 4
'asdfgh' panjangnya 6
Sebuah string kosong, biasanya dinyatakan dengan €, didefinisikan panjangnya = 0, atau |€| = 0 simbol untuk € dinyatakan dengan y kebalik. Suatu alphabet adalah himpunan berhingga dari simbol-simbol.
Pada umumnya kita mengenal bahasa alami, seperti bahasa inggris atau indonesia. Bahasa didefinisikan di dalam kamus adalah suatu sistem yang meliput pengekspresian gagasan, fakta, konsep, termasuk sekumpulan simbol-simbol dan aturan untuk melakukan manipulasi. Sebuah bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet. Karna sebuah bahasa adalah kumpulan dari string-string, yaitu bahasa kosong, bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {€}. Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna.
