Di era teknologi saat ini bidang perangkat keras dan perangkat lunak telah melihat perkembangan yang luar biasa. Salah satu bidang utama pengembangan terlihat dalam metode desain Perangkat Keras. Dengan teknologi berkembang , konsep Desain Bersama Perangkat Keras - Perangkat Lunak dapat diterapkan. Berbagai metode dikembangkan dimana, menggunakan perangkat lunak seseorang dapat sepenuhnya merancang dan mensimulasikan sistem perangkat keras. Salah satu metode tersebut adalah Teori Automata. Teori automata adalah cabang dari ilmu Komputer yang berhubungan dengan perancangan model abstrak perangkat komputasi yang mengikuti urutan langkah yang telah ditentukan secara otomatis. Artikel ini membahas informasi singkat tentang tutorial automata.
Apa itu Teori Automata?
Kata Automata berasal dari bahasa Yunani, yang berarti 'bertindak sendiri'. Automaton adalah model matematis mesin. Automaton terdiri dari status dan transisi. Saat input diberikan ke automaton, itu membuat transisi ke keadaan berikutnya, tergantung pada fungsi transisi. Input ke fungsi transisi adalah status sekarang dan simbol terkini. Jika Automaton memiliki jumlah status terbatas, itu dikenal sebagai Finite Automata atau Mesin Keadaan Hingga . Automata hingga diwakili oleh 5-tupel (Q, ∑, δ, qo, F)
Dimana,
Q = Kumpulan keadaan terbatas.
∑ = kumpulan simbol hingga juga disebut Alfabet dari automata.
δ = fungsi transisi.
qo = keadaan awal input.
F = himpunan keadaan akhir Q.
Terminologi Dasar Teori Automata
Beberapa terminologi dasar Teori Automata adalah-
1 . Alfabet : Kumpulan simbol yang terbatas dalam teori automata dikenal sebagai Alphabet. Diwakili oleh huruf himpunan {a, b, c, d, e,} disebut himpunan alfabet, sedangkan himpunan 'a', 'b', 'c', 'd', 'e' disebut simbol.
dua . Tali : Dalam automata, string adalah urutan simbol terbatas yang diambil dari kumpulan alfabet ∑, Misalnya, string S = 'adeaddadc' valid pada alfabet set∑ = {a, b, c, d, e,}.
3 . Panjang String : Jumlah simbol yang ada dalam string dikenal sebagai Panjang string. Untuk string S = 'adaada' panjang string adalah | S | = 6. Jika panjang stringnya 0, maka disebut string kosong.
4 . Kleen Star : Ini adalah operator unary pada himpunan simbol Σ, yang memberikan himpunan tak terhingga dari semua kemungkinan string, termasuk λ, dari semua panjang yang mungkin selama himpunan Σ. Ini diwakili oleh. Misalnya, untuk himpunan Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Penutupan Kleen : Ini himpunan tak terbatas dari semua kemungkinan string dari himpunan alfabet tidak termasuk λ. Ini dilambangkan dengan. Untuk himpunan Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Bahasa : Bahasa adalah himpunan bagian dari bintang Kleene set∑ * untuk beberapa himpunan Alfabet Σ. Bahasa bisa terbatas atau tidak terbatas. Misalnya jika suatu bahasa mengambil semua kemungkinan string dengan panjang 2 di atas himpunan Σ = {a, d}, maka L = {aa, ad, da, dd}.
Bahasa Formal dan Automata
Dalam teori automata, bahasa formal adalah sekumpulan string, di mana setiap string berada terdiri dari simbol milik himpunan Alfabet hingga Σ. Mari kita pertimbangkan bahasa kucing, yang dapat berisi string apa pun dari himpunan tak terbatas di bawah…
mengeong!
meww!
mengeong !! ……
Alfabet yang disetel untuk bahasa kucing adalah Σ = {m, e, w,!}. Biarkan set ini digunakan untuk Finite State Automata Model-m. Kemudian bahasa formal yang bercirikan model m dilambangkan dengan
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ……}
Automaton berguna untuk mendefinisikan suatu bahasa karena dapat mengekspresikan himpunan tak terhingga dalam bentuk tertutup. Bahasa formal tidak sama dengan bahasa alami yang kita gunakan dalam kehidupan sehari-hari. Bahasa formal dapat menunjukkan berbagai status mesin, tidak seperti bahasa reguler kami. Bahasa formal digunakan untuk memodelkan bagian dari bahasa alami seperti sintaks dll. Bahasa formal ditentukan oleh automata keadaan hingga. Ada dua perspektif utama automata keadaan Hingga- Akseptor yang dapat mengetahui apakah string ada dalam bahasa dan yang kedua adalah generator yang hanya menghasilkan string dalam bahasa tersebut.
Automata Hingga Deterministik
Dalam tipe Deterministik automata, ketika input diberikan, kita selalu dapat menentukan ke keadaan mana transisi itu akan. Karena ini adalah robot terbatas, ini disebut Deterministic Finite Automata.
Representasi grafis
Diagram Status adalah digraf yang digunakan untuk representasi grafis dari Deterministic Finite Automata. Mari kita pahami dengan sebuah contoh. Biarkan automata terbatas deterministik menjadi…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} dan fungsi transisi menjadi
Representasi Grafis Bentuk Tabular
Diagram Status
Diagram Keadaan dari Deterministic Finite State Automata
Dari diagram negara
- Negara bagian diwakili oleh simpul.
- Transisi diwakili oleh busur berlabel alfabet masukan.
- Busur masuk tunggal yang kosong mewakili keadaan awal.
- Negara bagian dengan lingkaran ganda adalah keadaan akhir.
Automata Hingga Non Deterministik
Automata di mana status keluaran untuk masukan yang diberikan tidak dapat ditentukan disebut Automata Non-Deterministik. Ia juga disebut Automata Terbatas Non-Deterministik, karena ia memiliki jumlah keadaan terbatas. Automata Hingga Non-deterministik direpresentasikan sebagai himpunan 5 –tuple di mana (Q, ∑, δ, qo, F)
Q = kumpulan negara yang terbatas.
∑ = Set alfabet.
δ = fungsi transisi
dimana : 
qo = Keadaan awal.
Representasi grafis
Automata terbatas non-deterministik diwakili dengan bantuan diagram keadaan. Biarkan Automata Hingga Non-Deterministik menjadi-
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Transisinya adalah
Representasi Grafis Bentuk Tabular
Diagram Status
Diagram Status Automata Hingga Non-Deterministik
Aplikasi Teori Automata
Aplikasi teori automata termasuk yang berikut ini.
- Teori automata sangat berguna di bidang Teori komputasi, produksi kompiler, AI, dll.
- Untuk kompiler pemrosesan teks dan desain perangkat keras, automata terbatas memainkan peran utama.
- Untuk aplikasi dalam AI dan dalam bahasa pemrograman , Tata bahasa tanpa konteks sangat berguna.
- Di bidang biologi, otomata seluler bermanfaat.
- Dalam teori bidang hingga juga kita dapat menemukan aplikasi Automata.
Pada artikel ini, kita telah mempelajari pengantar singkat tentang bahasa dan komputasi teori automata. Automata sudah ada sejak periode prasejarah. Dengan penemuan teknologi baru, banyak perkembangan baru terlihat di bidang ini. Jenis automata apa yang Anda temukan?
