Pada era teknologi hari ini, kedua-dua bidang perkakasan dan perisian telah menyaksikan perkembangan yang luar biasa. Salah satu bidang pengembangan utama dilihat pada kaedah reka bentuk Perkakasan. Dengan teknologi yang semakin meningkat , konsep Reka Bentuk Perisian - Perisian bersama mungkin dapat dilaksanakan. Kaedah yang berbeza dikembangkan di mana, menggunakan perisian seseorang dapat merancang dan mensimulasikan sistem perkakasan sepenuhnya. Salah satu kaedah tersebut ialah Teori Automata. Teori automata adalah cabang dari Sains Komputer yang berkaitan dengan merancang model abstrak peranti pengkomputeran yang mengikut urutan langkah yang telah ditentukan secara automatik. Artikel ini membincangkan maklumat ringkas mengenai tutorial automata.
Apa itu Teori Automata?
Kata Automata berasal dari bahasa Yunani, yang bermaksud 'bertindak sendiri'. Automaton adalah model matematik mesin. Automaton terdiri daripada keadaan dan peralihan. Oleh kerana input diberikan kepada automaton, ia membuat peralihan ke keadaan berikutnya, bergantung pada fungsi peralihan. Input ke fungsi peralihan adalah keadaan keadaan dan simbol terkini. Sekiranya Automaton mempunyai bilangan negeri yang terbatas, ia dikenali sebagai Finite Automata atau Mesin Keadaan Terhingga . Automata terhingga diwakili oleh 5-tuple (Q, ∑, δ, qo, F)
Di mana,
Q = Set keadaan yang terhad.
Set = sekumpulan simbol terhingga juga disebut Alphabet automata.
δ = fungsi peralihan.
qo = keadaan awal input.
F = set keadaan akhir Q.
Terminologi Asas Teori Automata
Beberapa terminologi asas Teori Automata adalah-
1 . Huruf abjad : Sebilangan set simbol dalam teori automata dikenali sebagai Alphabet. Diwakili oleh huruf∑ set {a, b, c, d, e,} disebut set abjad, sedangkan huruf set 'a', 'b', 'c', 'd', 'e' disebut simbol.
dua . Tali : Dalam automata, rentetan adalah urutan simbol terhingga yang diambil dari set abjad ∑, Sebagai contoh, rentetan S = 'adeaddadc' berlaku pada set abjad∑ = {a, b, c, d, e,}
3 . Panjang tali : Bilangan simbol yang terdapat dalam tali dikenali sebagai Panjang tali. Untuk rentetan S = 'adaada' panjang tali ialah | S | = 6. Sekiranya panjang tali ialah 0, maka ia dipanggil tali kosong.
4 . Bintang Kleen : Ini adalah operator yang tidak berubah pada set simbol Σ, yang memberikan set tak terbatas dari semua rentetan yang mungkin, termasuk λ, semua panjang yang mungkin di atas set Σ. Ia diwakili oleh. Contohnya, untuk set Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Penutupan Kleen : Ini adalah set tak terhingga dari semua rentetan set abjad yang mungkin tidak termasuk λ. Ia dilambangkan oleh. Untuk set Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . Bahasa : Bahasa adalah subset dari set bintang Kleene∑ * untuk beberapa set Abjad Σ. Bahasa boleh terbatas atau tidak terbatas. Contohnya jika bahasa mengambil semua kemungkinan rentetan panjang 2 di atas set Σ = {a, d}, maka L = {aa, ad, da, dd}.
Bahasa Formal dan Automata
Dalam teori automata, bahasa formal adalah sekumpulan rentetan, di mana setiap rentetan berada terdiri daripada simbol kepunyaan kumpulan Huruf terhingga Σ. Mari kita pertimbangkan bahasa kucing, yang boleh mengandungi rentetan dari set tak terbatas di bawah ini ...
mew!
meww!
mewww !! ……
Set abjad untuk bahasa kucing ialah Σ = {m, e, w,!}. Biarkan set ini digunakan untuk Model Automata Negeri Terhingga-m. Kemudian bahasa formal yang dicirikan oleh model m dilambangkan dengan
L (m)
L (m) = {‘mew!’, ‘Meww!’, ‘Mewww’, ……}
Automaton berguna untuk mendefinisikan bahasa kerana dapat menyatakan set tak terbatas dalam bentuk tertutup. Bahasa formal tidak sama dengan bahasa semula jadi yang kita gunakan dalam kehidupan kita sehari-hari. Bahasa formal dapat menunjukkan keadaan mesin yang berbeza, tidak seperti bahasa biasa kita. Bahasa formal digunakan untuk memodelkan sebahagian daripada bahasa semula jadi seperti sintaks dan lain-lain ... Bahasa formal ditakrifkan oleh automata keadaan terhingga. Terdapat dua perspektif utama automata keadaan Terhingga - Penerima yang dapat mengetahui apakah rentetan dalam bahasa dan yang kedua adalah penjana yang hanya menghasilkan rentetan dalam bahasa.
Automata Terhad Deterministik
Dalam jenis automata Deterministik, ketika input diberikan, kita selalu dapat menentukan keadaan peralihan yang mana. Kerana ini adalah automatik terhingga, ia disebut Deterministic Finite Automata.
Perwakilan Grafik
State Diagram adalah digraf yang digunakan untuk gambaran grafik Deterministic Finite Automata. Mari kita fahami dengan contoh. Biarkan automatik terbatas deterministik menjadi…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} dan fungsi peralihan menjadi
Borang Jadual Perwakilan Grafik
Rajah Negeri
Gambarajah Negeri Automata Negeri Terhad Deterministik
Dari rajah keadaan
- Negeri diwakili oleh bucu.
- Peralihan diwakili oleh busur yang dilabelkan dengan abjad input.
- Arka masuk tunggal kosong mewakili keadaan awal.
- Negeri dengan bulatan berganda adalah negeri terakhir.
Automata Hingga Tidak Deterministik
Automata di mana keadaan output untuk input yang diberikan tidak dapat ditentukan disebut Non-Deterministic Automata. Ia juga disebut Non-Deterministic Finite Automata, kerana ia memiliki sejumlah negara. Automata Terhingga Non-deterministik ditunjukkan sebagai kumpulan 5 –tuple di mana (Q, ∑, δ, qo, F)
Q = set negeri terhingga.
∑ = Set abjad.
δ = fungsi peralihan
di mana : 
qo = Keadaan awal.
Perwakilan Grafik
Automata terhingga non-deterministik ditunjukkan dengan bantuan gambarajah keadaan. Biarkan Automata Tidak Berpastian-
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Peralihan adalah
Borang Jadual Perwakilan Grafik
Rajah Negeri
Nyatakan Diagram Automata Terhad Non-Deterministik
Aplikasi Teori Automata
Aplikasi dari teori automata sertakan perkara berikut.
- Teori automata sangat berguna dalam bidang Teori pengiraan, pengeluaran penyusun, AI, dll.
- Untuk penyusun pemprosesan teks dan reka bentuk perkakasan, automata terbatas memainkan peranan utama.
- Untuk aplikasi di AI dan di bahasa pengaturcaraan , Tatabahasa bebas konteks sangat berguna.
- Dalam bidang biologi, automata selular berguna.
- Dalam teori bidang terhingga juga kita dapat mencari aplikasi Automata.
Dalam artikel ini, kami telah mempelajari pengenalan ringkas mengenai bahasa dan pengiraan teori automata. Automata telah wujud sejak zaman prasejarah. Dengan penemuan teknologi baru banyak perkembangan baru dilihat dalam bidang ini. Jenis automata apa yang anda temui?
