The Central Concepts of Automata Theory

Automata merupakan salah satu materi yang diajarkan di dalam jurusan Ilmu Komputer, termasuk saya sendiri hehehe. Automata memungkinkan mesin untuk mengenali, bahkan menghasilkan kalimat dalam bahasa tertentu. Automata juga bisa dijadikan model untuk merancang sirkuit digital, model untuk lexycal analyzer dari compiler. Berikut merupakan konsep dasar teori automata :

Symbol

Entitas abstrak yang tidak memiliki arti.

Contohnya :

• Huruf : A, .., Z, a, .., z
• Angka : 0..9
• Karakter Spesial : $, ∈, =, (, dll.

Alphabet (∑)

Kumpulan dari symbols. Dinotasikan dengan ∑.

• ∑ = {0, 1}, binary alphabets
• ∑ = {a, b, ..., z}, lower-case alphabets

Strings

Kombinasi symbols yang diambil dari alphabets. Contohnya string 001 diambil dari binary alphabets ∑ = {0, 1}, string 101100 juga diambil dari alphabets yang sama.

Empty String

String kosong yang tidak memiliki symbol apapun. Dinotasikan ε.

Length of String

Panjang string yang dimiliki. Misalnya string 101 memiliki length = 3. Length of string w dinotasikan dengan |w|. Misalnya |101| = 3 dan |ε| = 0

Power of Alphabet

Jika ∑ adalah alphabet, maka ∑^k adalah kumpulan strings dengan length k. Misalnya

• ∑ = {0, 1}, ∑¹ = {0, 1},  ∑² = {00, 01, 10, 11}, ∑⁰ = {ε}

Jika ingin menghasilkan semua kombinasi dari alphabet, dapat menggunakan ∑^*, misalnya

• {0,1}^* = {ε, 0, 1, 00, 10, 01, 11, 000, ...}

Jika ingin mengeliminasi empty string, dapat menggunakan ∑⁺, misalnya

• {0,1}⁺ = {0, 1, 00, 10, 01, 11, 000, ...}

Dapat disimpulkan bahwa

• ∑⁺ = ∑¹ ∪ ∑² ∪ ∑³ ∪ ...
• ∑^* = ∑⁺ ∪ {ε}

Concatenation of Strings

Jika x dan y adalah string. Maka xy adalah gabungan string dari x dan y. Misalnya

• x = 0001 dan y = 10, maka xy = 000110, maka yx = 100001

Language

Kumpulan strings yang memenuhi syarat tertentu. Contohnya :

• ∑^* adalah language untuk apapun alphabet ∑
• ∅ adalah language untuk himpunan kosong, tidak memiliki anggota
• {ε} adalah language yang hanya mengandung empty string, berbeda dengan ∅
• {10, 11, 101, 111, ...} adalah language yang hasilnya adalah bilangan prima
• {ε, 01, 0011, 000111, ...} adalah language yang mengandung n angka 0 diikuti oleh n angka 1

Sumber : Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. (2007). Introduction to automata theory, languages, and computation. 3rd. Addison-Wesley. New York. ISBN: 9780321476173, Chapter 1.1 (page 1-5) and 1.5 (page 28-34)