Teori Bahasa dan Automata: Terminologi, dan Aplikasi
Di era teknologi saat ini bidang perangkat keras dan perangkat lunak telah mengalami perkembangan yang luar biasa. Salah satu bidang utama pengembangan terlihat dalam metode desain Perangkat Keras. Dengan teknologi yang berkembang, konsep co-desain Perangkat Keras - Perangkat Lunak dimungkinkan untuk diterapkan.
Berbagai metode dikembangkan dimana, dengan menggunakan perangkat lunak seseorang dapat sepenuhnya merancang dan mensimulasikan sistem perangkat keras. Salah satu metode tersebut adalah Teori Automata.
Teori Automata adalah cabang ilmu komputer yang berkaitan dengan merancang model abstrak perangkat komputasi yang mengikuti urutan langkah-langkah yang telah ditentukan secara otomatis. Artikel ini membahas informasi singkat tentang tutorial teori automata.
Input ke fungsi transisi adalah simbol keadaan sekarang dan terkini. Jika suatu Automaton memiliki sejumlah keadaan terbatas, ia dikenal sebagai Automata Terbatas atau Mesin Keadaan Terbatas. Automata terbatas diwakili oleh 5-tupel (Q, Σ, δ, qo, F)
Dimana,
Q = Set keadaan terbatas.
∑ = kumpulan simbol hingga juga disebut Alfabet automata.
δ = fungsi transisi.
qo = keadaan awal input.
F = set keadaan akhir Q.
1. Alfabet : Setiap rangkaian simbol yang terbatas dalam teori automata dikenal sebagai Alfabet. Diwakili oleh huruf Σ, himpunan {a, b, c, d, e,} disebut himpunan alfabet, sedangkan huruf himpunan 'a', 'b', 'c', 'c', 'd', 'e' disebut simbol.
2. String (Tali) : Dalam automata, string adalah urutan terbatas dari simbol yang diambil dari himpunan alfabet, Σ, Misalnya, string S = 'adeaddadc' valid pada himpunan alfabet = {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 string adalah 0, maka itu disebut string kosong.
4. Kleen Star : Ini adalah operator unary pada himpunan simbol Σ, yang memberikan himpunan tak terbatas dari semua string yang mungkin, termasuk λ, dari semua panjang yang mungkin di atas himpunan Σ. Diwakili oleh. Misalnya, untuk set Σ = {c, d}, Σ* = {λ, c, d, cd, dc, cc, dd, ……}.
5. Kleen Closure : Ini adalah himpunan tak terbatas dari semua string alfabet yang mungkin tidak termasuk λ. Ini dilambangkan dengan. Untuk set Σ = {a, d}, Σ+ = {a, d, iklan, da, aa, dd,…..}.
6. Bahasa : Bahasa adalah bagian dari set Kleene star Σ * untuk beberapa set Alfabet set Σ. Bahasa dapat terbatas atau tidak terbatas. Misalnya jika suatu bahasa mengambil semua string panjang 2 yang mungkin di atas set Σ = {a, d}, maka L = {aa, ad, da, dd}.
mew!
weww!
mewww !! ……
Set alfabet untuk bahasa kucing adalah Σ = {m, e, w,!}. Biarkan set ini digunakan untuk Keadaan Terbatas Automata Model-m. Kemudian bahasa formal yang dicirikan oleh model m dilambangkan dengan
L (m)
L (m) = {'mew!', 'meww!', 'mewww', ……}
Automaton berguna untuk mendefinisikan bahasa karena dapat mengekspresikan set yang tak terbatas dalam bentuk tertutup. Bahasa formal tidak sama dengan bahasa alami yang kita gunakan sehari-hari. Bahasa formal dapat menunjukkan berbagai kondisi mesin, tidak seperti bahasa reguler kita.
Bahasa formal digunakan untuk memodelkan bagian dari bahasa alami seperti sintaksis dll. Bahasa formal didefinisikan oleh keadaan terbatas automata. Ada dua perspektif utama automata keadaan terbatas - akseptor yang dapat mengetahui apakah string dalam bahasa dan yang kedua adalah generator yang hanya menghasilkan string dalam bahasa.
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} dan fungsi transisi menjadi
Diagram Keadaan Deterministik Automata Terbatas
Dari diagram keadaan
Q = Set keadaan terbatas.
Σ = Kumpulan alfabet.
δ = Fungsi transisi
dimana
δ : Q x Σ → 2Q
qo = Keadaan awal.
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Transisinya adalah
Berbagai metode dikembangkan dimana, dengan menggunakan perangkat lunak seseorang dapat sepenuhnya merancang dan mensimulasikan sistem perangkat keras. Salah satu metode tersebut adalah Teori Automata.
Teori Automata adalah cabang ilmu komputer yang berkaitan dengan merancang model abstrak perangkat komputasi yang mengikuti urutan langkah-langkah yang telah ditentukan secara otomatis. Artikel ini membahas informasi singkat tentang tutorial teori automata.
Apa itu Teori Automata?
Kata Automata berasal dari bahasa Yunani, yang berarti "bertindak sendiri". Automaton adalah model matematika dari mesin. Automaton terdiri dari keadaan dan transisi. Karena input diberikan ke otomat, ia membuat transisi ke keadaan berikutnya, tergantung pada fungsi transisi.Input ke fungsi transisi adalah simbol keadaan sekarang dan terkini. Jika suatu Automaton memiliki sejumlah keadaan terbatas, ia dikenal sebagai Automata Terbatas atau Mesin Keadaan Terbatas. Automata terbatas diwakili oleh 5-tupel (Q, Σ, δ, qo, F)
Dimana,
Q = Set keadaan terbatas.
∑ = kumpulan simbol hingga juga disebut Alfabet automata.
δ = fungsi transisi.
qo = keadaan awal input.
F = set keadaan akhir Q.
Terminologi Dasar Teori Automata
Beberapa terminologi dasar dari teori Automata adalah1. Alfabet : Setiap rangkaian simbol yang terbatas dalam teori automata dikenal sebagai Alfabet. Diwakili oleh huruf Σ, himpunan {a, b, c, d, e,} disebut himpunan alfabet, sedangkan huruf himpunan 'a', 'b', 'c', 'c', 'd', 'e' disebut simbol.
2. String (Tali) : Dalam automata, string adalah urutan terbatas dari simbol yang diambil dari himpunan alfabet, Σ, Misalnya, string S = 'adeaddadc' valid pada himpunan alfabet = {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 string adalah 0, maka itu disebut string kosong.
4. Kleen Star : Ini adalah operator unary pada himpunan simbol Σ, yang memberikan himpunan tak terbatas dari semua string yang mungkin, termasuk λ, dari semua panjang yang mungkin di atas himpunan Σ. Diwakili oleh. Misalnya, untuk set Σ = {c, d}, Σ* = {λ, c, d, cd, dc, cc, dd, ……}.
5. Kleen Closure : Ini adalah himpunan tak terbatas dari semua string alfabet yang mungkin tidak termasuk λ. Ini dilambangkan dengan. Untuk set Σ = {a, d}, Σ+ = {a, d, iklan, da, aa, dd,…..}.
6. Bahasa : Bahasa adalah bagian dari set Kleene star Σ * untuk beberapa set Alfabet set Σ. Bahasa dapat terbatas atau tidak terbatas. Misalnya jika suatu bahasa mengambil semua string panjang 2 yang mungkin di atas set Σ = {a, d}, maka L = {aa, ad, da, dd}.
Bahasa Formal dan Automata
Dalam teori automata, bahasa formal adalah seperangkat string, di mana setiap string terdiri dari simbol milik set alfabet terbatas Σ. Mari kita bahas bahasa kucing, yang dapat berisi string apa pun dari rangkaian tak terbatas di bawah ini...mew!
weww!
mewww !! ……
Set alfabet untuk bahasa kucing adalah Σ = {m, e, w,!}. Biarkan set ini digunakan untuk Keadaan Terbatas Automata Model-m. Kemudian bahasa formal yang dicirikan oleh model m dilambangkan dengan
L (m)
L (m) = {'mew!', 'meww!', 'mewww', ……}
Automaton berguna untuk mendefinisikan bahasa karena dapat mengekspresikan set yang tak terbatas dalam bentuk tertutup. Bahasa formal tidak sama dengan bahasa alami yang kita gunakan sehari-hari. Bahasa formal dapat menunjukkan berbagai kondisi mesin, tidak seperti bahasa reguler kita.
Bahasa formal digunakan untuk memodelkan bagian dari bahasa alami seperti sintaksis dll. Bahasa formal didefinisikan oleh keadaan terbatas automata. Ada dua perspektif utama automata keadaan terbatas - akseptor yang dapat mengetahui apakah string dalam bahasa dan yang kedua adalah generator yang hanya menghasilkan string dalam bahasa.
Automata Terbatas Deterministik
Dalam tipe Deterministik automata, ketika input diberikan, kita selalu dapat menentukan keadaan transisi yang akan ditentukan. Karena ini adalah robot terbatas, itu disebut Deterministik Automata Terbatas.Representasi Grafis
Keadaan Diagram adalah diagram grafik yang digunakan untuk representasi grafis dari Deterministik Automata Terbatas. Mari kita pahami dengan sebuah contoh. Biarkan deterministik automata terbatas menjadi...Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} dan fungsi transisi menjadi
Keadaan
saat ini
|
Keadaan
Selanjutnya Untuk Input 0
|
Keadaan
Selanjutnya Untuk Input 0
|
a
|
a
|
b
|
b
|
b
|
c
|
c
|
c
|
d
|
d
|
d
|
a
|
Diagram Keadaan
Diagram Keadaan Deterministik Automata Terbatas
Dari diagram keadaan
- Keadaan-keadaan diwakili oleh simpul.
- Transisi diwakili oleh busur berlabel alfabet input.
- Busur masuk tunggal kosong mewakili kondisi awal.
- Keadaan dengan lingkaran ganda adalah keadaan terakhir.
Automata Terbatas Non Deterministik
Automata di mana keadaan output untuk input yang diberikan tidak dapat ditentukan disebut Non-Deterministik Automata. Itu juga disebut Automata Terbatas Non-Deterministik, karena ia memiliki sejumlah keadaan yang terbatas. Automata Terbatas Non-Deterministik direpresentasikan sebagai himpunan 5 –tuple dimana (Q,, δ, qo, F)Q = Set keadaan terbatas.
Σ = Kumpulan alfabet.
δ = Fungsi transisi
dimana
δ : Q x Σ → 2Q
qo = Keadaan awal.
Representasi Grafis
Automata terbatas non-deterministik diwakili dengan bantuan diagram keadaan. Biarkan Automata Hingga Non-Deterministik menjadiQ = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Transisinya adalah
Keadaan
saat ini
|
Keadaan
Selanjutnya Untuk Input 0
|
Keadaan
Selanjutnya Untuk Input
|
a
|
a, b
|
b
|
b
|
b
|
b, c
|
c
|
c, d
|
d
|
d
|
d
|
d, a
|
Diagram Keadaan
Aplikasi Teori Automata
Aplikasi teori automata meliputi yang berikut ini.- Teori Automata sangat berguna dalam 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 bahasa pemrograman, tata bahasa bebas konteks sangat berguna.
- Di bidang biologi, Seluler automata berguna.
- Dalam teori bidang hingga juga kita dapat menemukan aplikasi Automata.