Mesin finite-state: Perbedaan antara revisi
Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.2 |
k clean up, replaced: {{Yatim → {{orphan |
||
Baris 1: | Baris 1: | ||
{{ |
{{orphan|Oktober 2022}} |
||
{{redirect|Mesin keadaan|mesin keadaan-terbatas|Sistem transisi|Metologi toleransi-kesalahan|Replika mesin keadaan}} |
{{redirect|Mesin keadaan|mesin keadaan-terbatas|Sistem transisi|Metologi toleransi-kesalahan|Replika mesin keadaan}} |
||
{{redirect|SFSM|perusahaan kereta api Italia|Circumvesuviana}} |
{{redirect|SFSM|perusahaan kereta api Italia|Circumvesuviana}} |
||
Baris 7: | Baris 7: | ||
{{Automata theory}} |
{{Automata theory}} |
||
Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah [[model komputasi matematis]]. FSM merupakan sebuah [[mesin abstrak]] yang dapat berada tepat di salah satu dari sejumlah finite-[[states]] pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa [[masukan]]; perubahan dari satu state ke state lain disebut ''transition''.<ref>{{Cite book|last=Wang|first=Jiacun|year=2019|title=Formal Methods in Computer Science|publisher=CRC Press|isbn=978-1-4987-7532-8|pages=34}}</ref> FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik].<ref>{{cite web|title=Finite State Machines – Brilliant Math & Science Wiki|url=https://brilliant.org/wiki/finite-state-machines/|website=brilliant.org|access-date=14 April 2018}}</ref> Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun. |
'''Mesin finite-state''' (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah [[model komputasi matematis]]. FSM merupakan sebuah [[mesin abstrak]] yang dapat berada tepat di salah satu dari sejumlah finite-[[states]] pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa [[masukan]]; perubahan dari satu state ke state lain disebut ''transition''.<ref name="Wang 2019 34">{{Cite book|last=Wang|first=Jiacun|year=2019|title=Formal Methods in Computer Science|publisher=CRC Press|isbn=978-1-4987-7532-8|pages=34}}</ref> FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik].<ref name="brilliant.org">{{cite web|title=Finite State Machines – Brilliant Math & Science Wiki|url=https://brilliant.org/wiki/finite-state-machines/|website=brilliant.org|access-date=14 April 2018}}</ref> Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun. |
||
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah [[mesin penjual otomatis]], yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, [[elevators]], yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, [[lampu lalu lintas]], yang mengubah urutan saat mobil menunggu, dan [[kunci kombinasi]], yang memerlukan masukan urutan angka dalam urutan yang benar. |
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah [[mesin penjual otomatis]], yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, [[elevators]], yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, [[lampu lalu lintas]], yang mengubah urutan saat mobil menunggu, dan [[kunci kombinasi]], yang memerlukan masukan urutan angka dalam urutan yang benar. |
||
Baris 65: | Baris 65: | ||
=== Keadaan/Table Acara === |
=== Keadaan/Table Acara === |
||
Beberapa tipe [[tabel state transisi |
Beberapa tipe [[tabel state transisi]] digunakan. Representasi yang paling umum ditunjukkan di bawah ini: kombinasi keadaan saat ini (misalnya B) dan masukan (misalnya Y) menunjukkan keadaan berikutnya (misalnya C). Informasi tindakan lengkap tidak langsung dijelaskan dalam tabel dan hanya dapat ditambahkan menggunakan catatan kaki. Definisi FSM termasuk informasi tindakan penuh dimungkinkan menggunakan [[tabel state]] (lihat juga [[FSM virtual]]). |
||
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;" |
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;" |
||
Baris 120: | Baris 120: | ||
'''Akseptor''' (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah [[urutan simbol]] (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7. |
'''Akseptor''' (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah [[urutan simbol]] (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7. |
||
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut [[bahasa formal]], adalah [[bahasa biasa]] jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.<ref>{{Cite book|last=Hopcroft|first=John E.|date=1979|url=https://www.worldcat.org/oclc/4549363|title=Introduction to automata theory, languages, and computation|location=Reading, Mass.|publisher=Addison-Wesley|isbn=0-201-02988-X|others=Jeffrey D. Ullman|oclc=4549363}}</ref> |
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut [[bahasa formal]], adalah [[bahasa biasa]] jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.<ref name="Hopcroft 1979">{{Cite book|last=Hopcroft|first=John E.|date=1979|url=https://www.worldcat.org/oclc/4549363|title=Introduction to automata theory, languages, and computation|location=Reading, Mass.|publisher=Addison-Wesley|isbn=0-201-02988-X|others=Jeffrey D. Ullman|oclc=4549363}}</ref> |
||
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah [[bahasa biasa]]. |
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah [[bahasa biasa]]. |
||
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari [[masalah jalur aljabar]] — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen [[semiring]] (sewenang-wenang).<ref>{{Cite book|last=Pouly|first=Marc|date=2011|url=https://www.worldcat.org/oclc/757511533|title=Generic Inference : a Unifying Theory for Automated Reasoning|location=Hoboken, N.J.|publisher=Wiley|isbn=978-1-118-01087-7|others=Jürg Kohlas|oclc=757511533}}</ref><ref>{{Cite web|title=inta, 08 ART8.pdf|url=http://dx.doi.org/10.35486/at.v11i1.30.g18|website=dx.doi.org|access-date=2021-03-21}}</ref> |
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari [[masalah jalur aljabar]] — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen [[semiring]] (sewenang-wenang).<ref name="Pouly 2011">{{Cite book|last=Pouly|first=Marc|date=2011|url=https://www.worldcat.org/oclc/757511533|title=Generic Inference : a Unifying Theory for Automated Reasoning|location=Hoboken, N.J.|publisher=Wiley|isbn=978-1-118-01087-7|others=Jürg Kohlas|oclc=757511533}}</ref><ref>{{Cite web|title=inta, 08 ART8.pdf|url=http://dx.doi.org/10.35486/at.v11i1.30.g18|website=dx.doi.org|access-date=2021-03-21}}</ref> |
||
Contoh dari status menerima muncul pada Gambar 5: [[deterministic finite automaton]] (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0. |
Contoh dari status menerima muncul pada Gambar 5: [[deterministic finite automaton]] (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0. |
||
Baris 135: | Baris 135: | ||
=== Transduser === |
=== Transduser === |
||
{{Artikel Main|[[Finite-state transduser]]}} |
{{Artikel Main|[[Finite-state transduser]]}} |
||
[[Berkas:Fsm_Moore_model_door_control.svg|jmpl|Gambar. 6 Transduser FSM: contoh model Moore |
[[Berkas:Fsm_Moore_model_door_control.svg|jmpl|Gambar. 6 Transduser FSM: contoh model Moore]] |
||
[[Berkas:Fsm_mealy_model_door_control.svg|jmpl|Gambar. 7 FSM Transduser: Contoh model Mealy |
[[Berkas:Fsm_mealy_model_door_control.svg|jmpl|Gambar. 7 FSM Transduser: Contoh model Mealy]] |
||
'''Transduser''' |
'''Transduser''' |
||
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]]. |
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]]. |
||
Baris 156: | Baris 156: | ||
=== Determinisme === |
=== Determinisme === |
||
Perbedaan lebih lanjut adalah antara automata deterministik ([[DFA]]) dan non-deterministik ([[NFA]], [[GNFA]]). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma [[konstruksi powerset]] dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik. |
Perbedaan lebih lanjut adalah antara automata deterministik ([[DFA]]) dan non-deterministik ([[NFA]], [[GNFA]]). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma [[konstruksi powerset]] dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik. |
||
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.<ref>{{Cite journal|last=Brutscheck|first=M.|last2=Berger|first2=S.|last3=Franke|first3=M.|last4=Schwarzbacher|first4=A.T.|last5=Becker|first5=S.|date=2008|title=Structural division procedure for efficient IC analysis|url=http://dx.doi.org/10.1049/cp:20080632|journal=IET Irish Signals and Systems Conference (ISSC 2008)|publisher=IEE|doi=10.1049/cp:20080632|isbn=978-0-86341-931-7}}</ref> |
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.<ref name="Brutscheck 2008">{{Cite journal|last=Brutscheck|first=M.|last2=Berger|first2=S.|last3=Franke|first3=M.|last4=Schwarzbacher|first4=A.T.|last5=Becker|first5=S.|date=2008|title=Structural division procedure for efficient IC analysis|url=http://dx.doi.org/10.1049/cp:20080632|journal=IET Irish Signals and Systems Conference (ISSC 2008)|publisher=IEE|doi=10.1049/cp:20080632|isbn=978-0-86341-931-7}}</ref> |
||
== Alternatif semantik == |
== Alternatif semantik == |
||
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan [[mesin state hierarkis]] (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan [[tabel kebenaran]] ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.<ref>{{Cite journal|last=Hamon|first=Grégoire|date=2005|title=A denotational semantics for stateflow|url=http://dx.doi.org/10.1145/1086228.1086260|journal=Proceedings of the 5th ACM international conference on Embedded software - EMSOFT '05|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1086228.1086260|isbn=1-59593-091-4}}</ref> Bagan ini dapat menjadi seperti mesin state asli Harel,<ref>{{Cite journal|last=Harel|first=David|date=1987-06|title=Statecharts: a visual formalism for complex systems|url=http://dx.doi.org/10.1016/0167-6423(87)90035-9|journal=Science of Computer Programming|volume=8|issue=3|pages=231–274|doi=10.1016/0167-6423(87)90035-9|issn=0167-6423}}</ref> mendukung keadaan bertingkat secara hierarkis, [[daerah ortogonal]], tindakan keadaan, dan tindakan transisi.<ref>{{Cite journal|last=Alur|first=Rajeev|last2=Kanade|first2=Aditya|last3=Ramesh|first3=S.|last4=Shashidhar|first4=K. C.|date=2008|title=Symbolic analysis for improving simulation coverage of Simulink/Stateflow models|url=http://dx.doi.org/10.1145/1450058.1450071|journal=Proceedings of the 7th ACM international conference on Embedded software - EMSOFT '08|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1450058.1450071|isbn=978-1-60558-468-3}}</ref> |
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan [[mesin state hierarkis]] (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan [[tabel kebenaran]] ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.<ref name="Hamon 2005">{{Cite journal|last=Hamon|first=Grégoire|date=2005|title=A denotational semantics for stateflow|url=http://dx.doi.org/10.1145/1086228.1086260|journal=Proceedings of the 5th ACM international conference on Embedded software - EMSOFT '05|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1086228.1086260|isbn=1-59593-091-4}}</ref> Bagan ini dapat menjadi seperti mesin state asli Harel,<ref name="Harel 231–274">{{Cite journal|last=Harel|first=David|date=1987-06|title=Statecharts: a visual formalism for complex systems|url=http://dx.doi.org/10.1016/0167-6423(87)90035-9|journal=Science of Computer Programming|volume=8|issue=3|pages=231–274|doi=10.1016/0167-6423(87)90035-9|issn=0167-6423}}</ref> mendukung keadaan bertingkat secara hierarkis, [[daerah ortogonal]], tindakan keadaan, dan tindakan transisi.<ref name="Alur 2008">{{Cite journal|last=Alur|first=Rajeev|last2=Kanade|first2=Aditya|last3=Ramesh|first3=S.|last4=Shashidhar|first4=K. C.|date=2008|title=Symbolic analysis for improving simulation coverage of Simulink/Stateflow models|url=http://dx.doi.org/10.1145/1450058.1450071|journal=Proceedings of the 7th ACM international conference on Embedded software - EMSOFT '08|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1450058.1450071|isbn=978-1-60558-468-3}}</ref> |
||
== Model Matematika == |
== Model Matematika == |
||
Baris 189: | Baris 189: | ||
Jika fungsi keluaran bergantung dari status dan simbol masukan (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan (<math>\omega: S \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai [[mesin Moore]]. FSM tanpa fungsi keluaran sama sekali dikenal sebagai [[semi-otomatis]] atau sistem [[sistem transisi]]. |
Jika fungsi keluaran bergantung dari status dan simbol masukan (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan (<math>\omega: S \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai [[mesin Moore]]. FSM tanpa fungsi keluaran sama sekali dikenal sebagai [[semi-otomatis]] atau sistem [[sistem transisi]]. |
||
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, <math>\omega(s_0)</math>, maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.<ref>{{Cite book|last=Anderson|first=James A.|date=2006|url=https://www.worldcat.org/oclc/607557660|title=Automata theory with modern applications|location=Cambridge|publisher=Cambridge University Press|isbn=978-0-511-64856-4|others=Thomas J. Head|oclc=607557660}}</ref> |
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, <math>\omega(s_0)</math>, maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.<ref name="Anderson 2006">{{Cite book|last=Anderson|first=James A.|date=2006|url=https://www.worldcat.org/oclc/607557660|title=Automata theory with modern applications|location=Cambridge|publisher=Cambridge University Press|isbn=978-0-511-64856-4|others=Thomas J. Head|oclc=607557660}}</ref> |
||
== Optimisasi == |
== Optimisasi == |
||
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah algoritma minimisasi Hopcroft.<ref>{{Cite book|last=Hopcroft|first=John|date=1971|url=http://dx.doi.org/10.1016/b978-0-12-417750-5.50022-1|title=Theory of Machines and Computations|publisher=Elsevier|isbn=978-0-12-417750-5|pages=189–196}}</ref><ref>{{Cite book|last=Almeida|first=André|last2=Almeida|first2=Marco|last3=Alves|first3=José|last4=Moreira|first4=Nelma|last5=Reis|first5=Rogério|date=2009|url=http://dx.doi.org/10.1007/978-3-642-02979-0_10|title=Implementation and Application of Automata|location=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|isbn=978-3-642-02978-3|pages=65–74}}</ref> Teknik lain ini termasuk menggunakan tabel implikasi, atau prosedur pengurangan Moore. Selain itu, FSA asiklik dapat diminimalkan dalam waktu linier.<ref>{{Cite journal|last=Revuz|first=Dominique|date=1992-01|title=Minimisation of acyclic deterministic automata in linear time|url=https://linkinghub.elsevier.com/retrieve/pii/0304397592901423|journal=Theoretical Computer Science|language=en|volume=92|issue=1|pages=181–189|doi=10.1016/0304-3975(92)90142-3}}</ref> |
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah algoritma minimisasi Hopcroft.<ref name="Hopcroft 1971 189–196">{{Cite book|last=Hopcroft|first=John|date=1971|url=http://dx.doi.org/10.1016/b978-0-12-417750-5.50022-1|title=Theory of Machines and Computations|publisher=Elsevier|isbn=978-0-12-417750-5|pages=189–196}}</ref><ref name="Almeida 2009 65–74">{{Cite book|last=Almeida|first=André|last2=Almeida|first2=Marco|last3=Alves|first3=José|last4=Moreira|first4=Nelma|last5=Reis|first5=Rogério|date=2009|url=http://dx.doi.org/10.1007/978-3-642-02979-0_10|title=Implementation and Application of Automata|location=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|isbn=978-3-642-02978-3|pages=65–74}}</ref> Teknik lain ini termasuk menggunakan tabel implikasi, atau prosedur pengurangan Moore. Selain itu, FSA asiklik dapat diminimalkan dalam waktu linier.<ref name="Revuz 181–189">{{Cite journal|last=Revuz|first=Dominique|date=1992-01|title=Minimisation of acyclic deterministic automata in linear time|url=https://linkinghub.elsevier.com/retrieve/pii/0304397592901423|journal=Theoretical Computer Science|language=en|volume=92|issue=1|pages=181–189|doi=10.1016/0304-3975(92)90142-3}}</ref> |
||
== Implementasi == |
== Implementasi == |
||
Baris 200: | Baris 200: | ||
Dalam sirkuit digital, FSM dapat dibangun menggunakan perangkat logika yang dapat diprogram, pengontrol logika yang dapat diprogram, gerbang logika dan flip flop atau relay. Lebih khusus lagi, implementasi perangkat keras memerlukan regristasi untuk menyimpan variabel status, blok logika kombinasional yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah pengontrol Richards. |
Dalam sirkuit digital, FSM dapat dibangun menggunakan perangkat logika yang dapat diprogram, pengontrol logika yang dapat diprogram, gerbang logika dan flip flop atau relay. Lebih khusus lagi, implementasi perangkat keras memerlukan regristasi untuk menyimpan variabel status, blok logika kombinasional yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah pengontrol Richards. |
||
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.<ref>{{cite book|last=Kaeslin|first=Hubert|year=2008|title=Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication|publisher=Cambridge University Press|isbn=978-0-521-88267-5|page=787|chapter=Mealy, Moore, Medvedev-type and combinatorial output bits|chapter-url=https://books.google.com/books?id=gdRStcYgf2oC&q=medvedev+fsm&pg=PA787}}</ref><ref>[http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf Slides] {{Webarchive|url=https://web.archive.org/web/20170118123034/http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf|date=18 January 2017}}, ''Synchronous Finite State Machines; Design and Behaviour'', [[University of Applied Sciences Hamburg]], p.18</ref> |
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.<ref name="Kaeslin 2008 787">{{cite book|last=Kaeslin|first=Hubert|year=2008|title=Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication|publisher=Cambridge University Press|isbn=978-0-521-88267-5|page=787|chapter=Mealy, Moore, Medvedev-type and combinatorial output bits|chapter-url=https://books.google.com/books?id=gdRStcYgf2oC&q=medvedev+fsm&pg=PA787}}</ref><ref>[http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf Slides] {{Webarchive|url=https://web.archive.org/web/20170118123034/http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf|date=18 January 2017}}, ''Synchronous Finite State Machines; Design and Behaviour'', [[University of Applied Sciences Hamburg]], p.18</ref> |
||
Melalui pengkodean status untuk mesin dengan status daya rendah dapat dioptimalkan untuk meminimalkan konsumsi daya. |
Melalui pengkodean status untuk mesin dengan status daya rendah dapat dioptimalkan untuk meminimalkan konsumsi daya. |
||
Baris 211: | Baris 211: | ||
{{Automata theory}} |
{{Automata theory}} |
||
Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah [[model komputasi matematis]]. FSM merupakan sebuah [[mesin abstrak]] yang dapat berada tepat di salah satu dari sejumlah finite-[[states]] pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa [[masukan]]; perubahan dari satu state ke state lain disebut ''transition''.<ref |
Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah [[model komputasi matematis]]. FSM merupakan sebuah [[mesin abstrak]] yang dapat berada tepat di salah satu dari sejumlah finite-[[states]] pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa [[masukan]]; perubahan dari satu state ke state lain disebut ''transition''.<ref name="Wang 2019 34"/> FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik].<ref name="brilliant.org"/> Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun. |
||
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah [[mesin penjual otomatis]], yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, [[elevators]], yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, [[lampu lalu lintas]], yang mengubah urutan saat mobil menunggu, dan [[kunci kombinasi]], yang memerlukan masukan urutan angka dalam urutan yang benar. |
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah [[mesin penjual otomatis]], yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, [[elevators]], yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, [[lampu lalu lintas]], yang mengubah urutan saat mobil menunggu, dan [[kunci kombinasi]], yang memerlukan masukan urutan angka dalam urutan yang benar. |
||
Baris 269: | Baris 269: | ||
=== Keadaan/Table Acara === |
=== Keadaan/Table Acara === |
||
Beberapa tipe [[tabel state transisi |
Beberapa tipe [[tabel state transisi]] digunakan. Representasi yang paling umum ditunjukkan di bawah ini: kombinasi keadaan saat ini (misalnya B) dan masukan (misalnya Y) menunjukkan keadaan berikutnya (misalnya C). Informasi tindakan lengkap tidak langsung dijelaskan dalam tabel dan hanya dapat ditambahkan menggunakan catatan kaki. Definisi FSM termasuk informasi tindakan penuh dimungkinkan menggunakan [[tabel state]] (lihat juga [[FSM virtual]]). |
||
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;" |
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;" |
||
Baris 324: | Baris 324: | ||
'''Akseptor''' (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah [[urutan simbol]] (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7. |
'''Akseptor''' (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah [[urutan simbol]] (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7. |
||
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut [[bahasa formal]], adalah [[bahasa biasa]] jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.<ref |
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut [[bahasa formal]], adalah [[bahasa biasa]] jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.<ref name="Hopcroft 1979"/> |
||
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah [[bahasa biasa]]. |
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah [[bahasa biasa]]. |
||
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari [[masalah jalur aljabar]] — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen [[semiring]] (sewenang-wenang).<ref |
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari [[masalah jalur aljabar]] — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen [[semiring]] (sewenang-wenang).<ref name="Pouly 2011"/><ref>{{Cite web|title=inta, 08 ART8.pdf|url=http://dx.doi.org/10.35486/at.v11i1.30.g18|website=dx.doi.org|access-date=2021-03-21}}</ref> |
||
Contoh dari status menerima muncul pada Gambar 5: [[deterministic finite automaton]] (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0. |
Contoh dari status menerima muncul pada Gambar 5: [[deterministic finite automaton]] (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0. |
||
Baris 339: | Baris 339: | ||
=== Transduser === |
=== Transduser === |
||
{{Artikel Main|[[Finite-state transduser]]}} |
{{Artikel Main|[[Finite-state transduser]]}} |
||
[[Berkas:Fsm_Moore_model_door_control.svg|jmpl|Gambar. 6 Transduser FSM: contoh model Moore |
[[Berkas:Fsm_Moore_model_door_control.svg|jmpl|Gambar. 6 Transduser FSM: contoh model Moore]] |
||
[[Berkas:Fsm_mealy_model_door_control.svg|jmpl|Gambar. 7 FSM Transduser: Contoh model Mealy |
[[Berkas:Fsm_mealy_model_door_control.svg|jmpl|Gambar. 7 FSM Transduser: Contoh model Mealy]] |
||
'''Transduser''' |
'''Transduser''' |
||
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]]. |
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]]. |
||
Baris 360: | Baris 360: | ||
=== Determinisme === |
=== Determinisme === |
||
Perbedaan lebih lanjut adalah antara automata deterministik ([[DFA]]) dan non-deterministik ([[NFA]], [[GNFA]]). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma [[konstruksi powerset]] dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik. |
Perbedaan lebih lanjut adalah antara automata deterministik ([[DFA]]) dan non-deterministik ([[NFA]], [[GNFA]]). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma [[konstruksi powerset]] dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik. |
||
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.<ref |
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.<ref name="Brutscheck 2008"/> |
||
== Alternatif semantik == |
== Alternatif semantik == |
||
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan [[mesin state hierarkis]] (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan [[tabel kebenaran]] ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.<ref |
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan [[mesin state hierarkis]] (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan [[tabel kebenaran]] ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.<ref name="Hamon 2005"/> Bagan ini dapat menjadi seperti mesin state asli Harel,<ref name="Harel 231–274"/> mendukung keadaan bertingkat secara hierarkis, [[daerah ortogonal]], tindakan keadaan, dan tindakan transisi.<ref name="Alur 2008"/> |
||
== Model Matematika == |
== Model Matematika == |
||
Baris 393: | Baris 393: | ||
Jika fungsi keluaran bergantung dari status dan simbol masukan (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan (<math>\omega: S \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai [[mesin Moore]]. FSM tanpa fungsi keluaran sama sekali dikenal sebagai [[semi-otomatis]] atau sistem [[sistem transisi]]. |
Jika fungsi keluaran bergantung dari status dan simbol masukan (<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan (<math>\omega: S \rightarrow \Gamma</math>) definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai [[mesin Moore]]. FSM tanpa fungsi keluaran sama sekali dikenal sebagai [[semi-otomatis]] atau sistem [[sistem transisi]]. |
||
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, <math>\omega(s_0)</math>, maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.<ref |
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, <math>\omega(s_0)</math>, maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.<ref name="Anderson 2006"/> |
||
== Optimisasi == |
== Optimisasi == |
||
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah [[algoritma minimisasi Hopcroft.]]<ref |
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah [[algoritma minimisasi Hopcroft.]]<ref name="Hopcroft 1971 189–196"/><ref name="Almeida 2009 65–74"/> Teknik lain ini termasuk menggunakan [[tabel implikasi]], atau prosedur pengurangan Moore. Selain itu, FSA asiklik dapat diminimalkan dalam waktu linier.<ref name="Revuz 181–189"/> |
||
== Implementasi == |
== Implementasi == |
||
Baris 404: | Baris 404: | ||
Dalam [[sirkuit digital]], FSM dapat dibangun menggunakan [[perangkat logika yang dapat diprogram]], [[pengontrol logika yang dapat diprogram]], [[gerbang logika]] dan [[flip flop]] atau [[relay]]. Lebih khusus lagi, implementasi perangkat keras memerlukan [[register]] untuk menyimpan variabel status, [[kombinasional blok logika]] yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah [[Richards Controller]]. |
Dalam [[sirkuit digital]], FSM dapat dibangun menggunakan [[perangkat logika yang dapat diprogram]], [[pengontrol logika yang dapat diprogram]], [[gerbang logika]] dan [[flip flop]] atau [[relay]]. Lebih khusus lagi, implementasi perangkat keras memerlukan [[register]] untuk menyimpan variabel status, [[kombinasional blok logika]] yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah [[Richards Controller]]. |
||
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.<ref |
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.<ref name="Kaeslin 2008 787"/><ref>[http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf Slides] {{Webarchive|url=https://web.archive.org/web/20170118123034/http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf|date=18 January 2017}}, ''Synchronous Finite State Machines; Design and Behaviour'', [[University of Applied Sciences Hamburg]], p.18</ref> |
||
Melalui [[pengkodean status untuk mesin dengan status daya rendah]] dapat dioptimalkan untuk meminimalkan konsumsi daya. |
Melalui [[pengkodean status untuk mesin dengan status daya rendah]] dapat dioptimalkan untuk meminimalkan konsumsi daya. |
||
Baris 417: | Baris 417: | ||
=== Mesin dan kompiler Keadaan-terbatas === |
=== Mesin dan kompiler Keadaan-terbatas === |
||
Automata terbatas sering digunakan di [[Front-end dan back-end|frontend]] kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, [[penganalisis leksikal]] membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.<ref>{{cite book|last1=Aho|first1=Alfred V.|last2=Sethi|first2=Ravi|last3=Ullman|first3=Jeffrey D.|year=1986|title=Compilers: Principles, Techniques, and Tools|title-link=Compilers: Principles, Techniques, and Tools|publisher=[[Addison-Wesley]]|isbn=978-0-201-10088-4|edition=1st|author-link1=Alfred V. Aho|author-link2=Ravi Sethi|author-link3=Jeffrey D. Ullman}}</ref> |
Automata terbatas sering digunakan di [[Front-end dan back-end|frontend]] kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, [[penganalisis leksikal]] membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.<ref name="Addison-Wesley">{{cite book|last1=Aho|first1=Alfred V.|last2=Sethi|first2=Ravi|last3=Ullman|first3=Jeffrey D.|year=1986|title=Compilers: Principles, Techniques, and Tools|title-link=Compilers: Principles, Techniques, and Tools|publisher=[[Addison-Wesley]]|isbn=978-0-201-10088-4|edition=1st|author-link1=Alfred V. Aho|author-link2=Ravi Sethi|author-link3=Jeffrey D. Ullman}}</ref> |
||
== Lihat Juga == |
== Lihat Juga == |
||
Baris 532: | Baris 531: | ||
{{Bahasa formal dan gramer}} |
{{Bahasa formal dan gramer}} |
||
{{sistem digital}} |
{{sistem digital}} |
||
=== Mesin dan kompiler Keadaan-terbatas === |
=== Mesin dan kompiler Keadaan-terbatas === |
||
Automata terbatas sering digunakan di bagian depan kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, penganalisis leksikal membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.<ref |
Automata terbatas sering digunakan di bagian depan kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, penganalisis leksikal membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.<ref name="Addison-Wesley"/> |
||
== Lihat Juga == |
== Lihat Juga == |
Revisi per 9 Januari 2023 20.33
Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini. Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala. Tag ini diberikan pada Oktober 2022. |
Templat:Deskripsi singkat Templat:Automata theory
Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah model komputasi matematis. FSM merupakan sebuah mesin abstrak yang dapat berada tepat di salah satu dari sejumlah finite-states pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa masukan; perubahan dari satu state ke state lain disebut transition.[1] FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik].[2] Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun.
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah mesin penjual otomatis, yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, elevators, yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, lampu lalu lintas, yang mengubah urutan saat mobil menunggu, dan kunci kombinasi, yang memerlukan masukan urutan angka dalam urutan yang benar.
Mesin finite-state memiliki daya komputasi yang lebih sedikit dibandingkan beberapa model komputasi lain seperti mesin Turing.[3] Perbedaan daya komputasi berarti ada tugas komputasi yang dapat dilakukan mesin Turing tetapi FSM tidak bisa. Ini karena memori FSM dibatasi oleh jumlah keadaan yang dimilikinya. Mesin keadaan-terbatas memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. FSM dipelajari di bidang teori automata yang lebih umum.
Contoh: pintu putar yang dioperasikan dengan koin
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Turnstile_state_machine_colored.svg/220px-Turnstile_state_machine_colored.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/9/97/Torniqueterevolution.jpg)
Contoh mekanisme sederhana yang dapat dimodelkan oleh mesin state adalah pintu putar.[4][5] Pintu putar, digunakan untuk mengontrol akses ke kereta bawah tanah dan wahana taman hiburan, adalah gerbang dengan tiga lengan berputar setinggi pinggang, satu di sebrang pintu masuk. Awalnya lengan terkunci, menghalangi jalan masuk, mencegah pengunjung lewat. Menyimpan koin atau token di slot di pintu putar akan membuka kunci lengan, memungkinkan satu pelanggan untuk mendorong. Setelah pelanggan melewatinya, lengannya dikunci lagi hingga koin lain dimasukkan.
Dianggap sebagai mesin state, pintu putar memiliki dua kemungkinan status: Terkunci dan Tidak Terkunci.[4] Ada dua kemungkinan masukan yang mempengaruhi statusnya: memasukkan koin ke dalam slot (koin) dan mendorong lengan (mendorong). Dalam keadaan terkunci, mendorong lengan tidak berpengaruh; tidak peduli berapa kali dorongan masukan diberikan, itu tetap dalam keadaan terkunci. Memasukkan koin - yaitu, memberi mesin masukan koin - akan menggeser status dari Terkunci ke Tidak Terkunci. Dalam keadaan tidak terkunci, memasukkan koin tambahan tidak berpengaruh; artinya, memberikan masukan koin tambahan tidak mengubah status. Namun, pelanggan mendorong lengan, memberikan masukan dorong, menggeser status kembali ke Terkunci.
Mesin state pintu pagar dapat diwakili oleh tabel transisi state, yang menunjukkan untuk setiap state yang mungkin, transisi di antara mereka (berdasarkan masukan yang diberikan ke mesin) dan keluaran yang dihasilkan dari setiap masukan:
Keadaan Sekarang Masukan State Berikutnya Keluaran Terkunci Koin Terbuka Membuka kunci pintu putar sehingga pelanggan dapat melewatinya. Mendorong Terkunci Tidak mengeluarkan apa apa Terbuka Koin Terbuka Tidak mengeluarkan apa apa Mendorong Terkunci Saat pelanggan telah mendorong, mengunci pintu putar.
Mesin state pintu putar juga dapat diwakili oleh grafik terarah yang disebut diagram state (di atas). Setiap state diwakili oleh sebuah node (lingkaran). Tepi (panah) menunjukkan transisi dari satu state ke state lain. Setiap panah diberi label dengan masukan yang memicu transisi itu. Masukan yang tidak menyebabkan perubahan state (seperti input koin dalam status Tidak Terkunci) diwakili oleh panah melingkar yang kembali ke keadaan semula. Panah ke simpul Terkunci dari titik hitam menunjukkan itu adalah state awal.
Konsep dan terminologi
Keadaan adalah deskripsi keadaan sistem yang menunggu untuk menjalankan transisi. Transisi adalah sekumpulan tindakan yang akan dijalankan saat kondisi terpenuhi atau saat peristiwa diterima. Misalnya, saat menggunakan sistem audio untuk mendengarkan radio (sistem dalam status "radio"), menerima hasil stimulus "berikutnya" untuk pindah ke stasiun berikutnya. Ketika sistem berada dalam status "CD", hasil stimulus "berikutnya" untuk pindah ke trek berikutnya. Rangsangan identik memicu tindakan yang berbeda tergantung pada keadaan saat ini.
Dalam beberapa representasi mesin keadaan-hingga, dimungkinkan juga untuk mengaitkan tindakan dengan keadaan:
- tindakan masuk: dilakukan saat memasuki keadaan, dan
- tindakan keluar: dilakukan saat keluar dari keadaan.
Representasi
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/UML_state_machine_Fig5.png/220px-UML_state_machine_Fig5.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/SdlStateMachine.png/220px-SdlStateMachine.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Finite_state_machine_example_with_comments.svg/220px-Finite_state_machine_example_with_comments.svg.png)
Keadaan/Table Acara
Beberapa tipe tabel state transisi digunakan. Representasi yang paling umum ditunjukkan di bawah ini: kombinasi keadaan saat ini (misalnya B) dan masukan (misalnya Y) menunjukkan keadaan berikutnya (misalnya C). Informasi tindakan lengkap tidak langsung dijelaskan dalam tabel dan hanya dapat ditambahkan menggunakan catatan kaki. Definisi FSM termasuk informasi tindakan penuh dimungkinkan menggunakan tabel state (lihat juga FSM virtual).
Keadaan sekarang Masukan
|
Keadaan A | Keadaan B | Keadaan C |
---|---|---|---|
Masukan X | ... | ... | ... |
Masukan Y | ... | Keadaan C | ... |
Masukan Z | ... | ... | ... |
UML mesin keadaan
Unified Modeling Language memiliki notasi untuk mendeskripsikan mesin state. Mesin state UML mengatasi keterbatasan FSM tradisional tetap mempertahankan manfaat utamanya. Mesin keadaan UML memperkenalkan konsep baru dengan state bertingkat hierarki dan wilayah ortogonal, sambil memperluas gagasan tindakan. Mesin state UML memiliki karakteristik mesin Mealy dan mesin Moore. Mereka mendukung tindakan yang bergantung pada status sistem dan peristiwa pemicu, seperti di mesin Mealy, serta tindakan masuk dan keluar, yang terkait dengan keadaan, bukan transisi, seperti di mesin Moore.
SDL mesin keadaan
Spesifikasi dan Deskripsi Bahasa adalah sebuah standar dari ITU yang menyertakan simbol grafis untuk menggambarkan tindakan dalam transisi:
- mengirim acara
- menerima sebuah acara
- mulai pengatur waktu
- batalkan pengatur waktu
- mulai mesin keadaan bersamaan dengan lainnya
- keputusan
SDL menyematkan tipe data dasar yang disebut "Tipe Data Abstrak", bahasa tindakan, dan semantik eksekusi untuk membuat mesin status hingga dapat dieksekusi.
Diagram keadaan lainnya
Ada banyak varian untuk mewakili FSM seperti yang ditunjukkan pada gambar 3.
Pemakaian
Selain penggunaannya dalam pemodelan sistem reaktif yang disajikan di sini, FSM penting di berbagai bidang, termasuk teknik kelistrikan, linguistik, ilmu komputer, filsafat, biologi, matematika, pemrograman video game, dan logika. FSM adalah sebuah kelas dari automata yang mempelajari dalam teori automata dan teori komputasi. Dalam ilmu komputer, FSM banyak digunakan dalam pemodelan perilaku aplikasi, desain sistem digital perangkat keras, rekayasa perangkat lunak, kompiler, protokol jaringan, dan studi komputasi dan bahasa.
Klasifikasi
Mesin keadaan-terbatas dapat dibagi lagi menjadi akseptor, pengklasifikasi, transduser, dan pengurut.[6]
Akseptor
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/220px-Fsm_parsing_word_nice.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/220px-DFAexample.svg.png)
Akseptor (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah urutan simbol (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7.
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut bahasa formal, adalah bahasa biasa jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.[7]
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah bahasa biasa.
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari masalah jalur aljabar — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen semiring (sewenang-wenang).[8][9]
Contoh dari status menerima muncul pada Gambar 5: deterministic finite automaton (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0.
S1 (yang juga merupakan status awal) menunjukkan status di mana bilangan genap 0 telah dimasukkan. Oleh karena itu S1 merupakan negara penerima. Akseptor ini akan selesai dalam status terima, jika string biner berisi bilangan genap 0 (termasuk string biner apa pun yang tidak berisi 0). Contoh string yang diterima oleh akseptor ini adalah ε (string kosong), 1, 11, 11 ..., 00, 010, 1010, 10110, dll.
Pengklasifikasi
Pengklasifikasi adalah generalisasi akseptor yang menghasilkan keluaran n-ary di mana n benar-benar lebih besar dari dua.
Transduser
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Fsm_Moore_model_door_control.svg/220px-Fsm_Moore_model_door_control.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Fsm_mealy_model_door_control.svg/220px-Fsm_mealy_model_door_control.svg.png)
Transduser Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang linguistik komputasi.
Dalam aplikasi kontrol, ada dua jenis yang dibedakan yaitu:
FSM hanya menggunakan tindakan entri, yaitu, keluaran hanya bergantung pada status. Keunggulan model Moore adalah penyederhanaan tingkah laku. Pertimbangkan pintu lift. Mesin negara mengenali dua perintah: "command_open" dan "command_close", yang memicu perubahan status. Tindakan entri (E :) dalam status "Membuka" memulai mesin membuka pintu, tindakan entri dalam status "Menutup" memulai mesin ke arah lain untuk menutup pintu. Menyatakan "Terbuka" dan "Tertutup" menghentikan motor saat dibuka atau ditutup penuh. Mereka memberi sinyal ke dunia luar (mis., Ke mesin keadaan lain) ke dalam situasi: "pintu terbuka" atau "pintu ditutup".
FSM hanya menggunakan tindakan entri, yaitu sebuah keluaran hanya bergantung pada status. Keunggulan model Moore adalah penyederhanaan tingkah laku mesin. Pertimbangkan pintu lift. Mesin state mengenali dua perintah: "command_open" dan "command_close", yang memicu perubahan state. Tindakan entri (E :) dalam status "Membuka" memulai mesin membuka pintu, tindakan entri dalam status "Menutup" memulai mesin ke arah lain untuk menutup pintu. Menyatakan "Terbuka" dan "Tertutup" menghentikan mesin saat dibuka atau ditutup penuh. Mereka memberi sinyal ke dunia luar (mis., Ke mesin state lain) ke dalam situasi: "pintu terbuka" atau "pintu ditutup".
Sequencer
Sequencer (juga disebut generator) adalah subkelas akseptor dan transduser yang memiliki alfabet masukan satu huruf. Mereka hanya menghasilkan satu urutan yang dapat dilihat sebagai urutan keluaran akseptor atau keluaran transduser.[6]
Determinisme
Perbedaan lebih lanjut adalah antara automata deterministik (DFA) dan non-deterministik (NFA, GNFA). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma konstruksi powerset dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik.
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.[10]
Alternatif semantik
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan mesin state hierarkis (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan tabel kebenaran ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.[11] Bagan ini dapat menjadi seperti mesin state asli Harel,[12] mendukung keadaan bertingkat secara hierarkis, daerah ortogonal, tindakan keadaan, dan tindakan transisi.[13]
Model Matematika
Sesuai dengan klasifikasi umum, definisi formal berikut ditemukan.
FSM deterministik atau akseptor FSM deterministik adalah kuintupel , di mana:
- adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);
- adalah yang digunakan sebagai alfabet himpunan status tak-kosong berhingga;
- adalah yang digunakan sebagai alfabet state awal, elemen dari ;
- adalah yang digunakan sebagai alfabet fungsi transisi-state: : (dalam robot berhingga non deterministik itu akan menjadi , i.e. akan mengembalikan satu set status);
- adalah yang digunakan sebagai alfabet himpunan state akhir, himpunan bagian (mungkin kosong) dari .
Untuk FSM deterministik dan non-deterministik, penggunaan adalah fungsi parsial, yaitu <math>\delta(s, x)</math> tidak harus ditentukan untuk setiap kombinasi dari dan . Jika FSM dalam keadaan , simbol berikutnya adalah dan tidak ditentukan, maka dapat mengumumkan kesalahan tersebut yaitu menolak input. Ini berguna dalam definisi mesin state umum, tetapi kurang berguna saat mengubah mesin. Beberapa algoritma dalam bentuk defaultnya mungkin memerlukan fungsi total.
FSM memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. Artinya, setiap bahasa formal yang diterima oleh FSM diterima oleh jenis mesin Turing yang dibatasi, dan sebaliknya.
Transduser FSM adalah sextuple , dimana:
- adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);
- adalah yang digunakan sebagai alfabet keluaran (kumpulan simbol tak kosong yang terbatas);
- adalah yang digunakan sebagai himpunan status tak-kosong berhingga;
- adalah yang digunakan sebagai state awal, elemen dari ;
- adalah yang digunakan sebagai fungsi transisi-keadaan: ;
- adalah yang digunakan sebagai fungsi keluaran.
Jika fungsi keluaran bergantung dari status dan simbol masukan () definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan () definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai mesin Moore. FSM tanpa fungsi keluaran sama sekali dikenal sebagai semi-otomatis atau sistem sistem transisi.
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, , maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.[14]
Optimisasi
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah algoritma minimisasi Hopcroft.[15][16] Teknik lain ini termasuk menggunakan tabel implikasi, atau prosedur pengurangan Moore. Selain itu, FSA asiklik dapat diminimalkan dalam waktu linier.[17]
Implementasi
Aplikasi perangkat keras
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/76/4_bit_counter.svg/220px-4_bit_counter.svg.png)
Dalam sirkuit digital, FSM dapat dibangun menggunakan perangkat logika yang dapat diprogram, pengontrol logika yang dapat diprogram, gerbang logika dan flip flop atau relay. Lebih khusus lagi, implementasi perangkat keras memerlukan regristasi untuk menyimpan variabel status, blok logika kombinasional yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah pengontrol Richards.
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.[18][19]
Melalui pengkodean status untuk mesin dengan status daya rendah dapat dioptimalkan untuk meminimalkan konsumsi daya.
Templat:Deskripsi singkat Templat:Automata theory
Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah model komputasi matematis. FSM merupakan sebuah mesin abstrak yang dapat berada tepat di salah satu dari sejumlah finite-states pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa masukan; perubahan dari satu state ke state lain disebut transition.[1] FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik].[2] Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun.
Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah mesin penjual otomatis, yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, elevators, yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, lampu lalu lintas, yang mengubah urutan saat mobil menunggu, dan kunci kombinasi, yang memerlukan masukan urutan angka dalam urutan yang benar.
Mesin finite-state memiliki daya komputasi yang lebih sedikit dibandingkan beberapa model komputasi lain seperti mesin Turing.[3] Perbedaan daya komputasi berarti ada tugas komputasi yang dapat dilakukan mesin Turing tetapi FSM tidak bisa. Ini karena memori FSM dibatasi oleh jumlah keadaan yang dimilikinya. Mesin keadaan-terbatas memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. FSM dipelajari di bidang teori automata yang lebih umum.
Contoh: pintu putar yang dioperasikan dengan koin
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Turnstile_state_machine_colored.svg/220px-Turnstile_state_machine_colored.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/9/97/Torniqueterevolution.jpg)
Contoh mekanisme sederhana yang dapat dimodelkan oleh mesin state adalah pintu putar.[4][5] Pintu putar, digunakan untuk mengontrol akses ke kereta bawah tanah dan wahana taman hiburan, adalah gerbang dengan tiga lengan berputar setinggi pinggang, satu di sebrang pintu masuk. Awalnya lengan terkunci, menghalangi jalan masuk, mencegah pengunjung lewat. Menyimpan koin atau token di slot di pintu putar akan membuka kunci lengan, memungkinkan satu pelanggan untuk mendorong. Setelah pelanggan melewatinya, lengannya dikunci lagi hingga koin lain dimasukkan.
Dianggap sebagai mesin state, pintu putar memiliki dua kemungkinan status: Terkunci dan Tidak Terkunci.[4] Ada dua kemungkinan masukan yang mempengaruhi statusnya: memasukkan koin ke dalam slot (koin) dan mendorong lengan (mendorong). Dalam keadaan terkunci, mendorong lengan tidak berpengaruh; tidak peduli berapa kali dorongan masukan diberikan, itu tetap dalam keadaan terkunci. Memasukkan koin - yaitu, memberi mesin masukan koin - akan menggeser status dari Terkunci ke Tidak Terkunci. Dalam keadaan tidak terkunci, memasukkan koin tambahan tidak berpengaruh; artinya, memberikan masukan koin tambahan tidak mengubah status. Namun, pelanggan mendorong lengan, memberikan masukan dorong, menggeser status kembali ke Terkunci.
Mesin state pintu pagar dapat diwakili oleh tabel transisi state, yang menunjukkan untuk setiap state yang mungkin, transisi di antara mereka (berdasarkan masukan yang diberikan ke mesin) dan keluaran yang dihasilkan dari setiap masukan:
Keadaan Sekarang Masukan State Berikutnya Keluaran Terkunci Koin Terbuka Membuka kunci pintu putar sehingga pelanggan dapat melewatinya. Mendorong Terkunci Tidak mengeluarkan apa apa Terbuka Koin Terbuka Tidak mengeluarkan apa apa Mendorong Terkunci Saat pelanggan telah mendorong, mengunci pintu putar.
Mesin state pintu putar juga dapat diwakili oleh grafik terarah yang disebut diagram state (di atas). Setiap state diwakili oleh sebuah node (lingkaran). Tepi (panah) menunjukkan transisi dari satu state ke state lain. Setiap panah diberi label dengan masukan yang memicu transisi itu. Masukan yang tidak menyebabkan perubahan state (seperti input koin dalam status Tidak Terkunci) diwakili oleh panah melingkar yang kembali ke keadaan semula. Panah ke simpul Terkunci dari titik hitam menunjukkan itu adalah state awal.
Konsep dan terminologi
Keadaan adalah deskripsi keadaan sistem yang menunggu untuk menjalankan transisi. Transisi adalah sekumpulan tindakan yang akan dijalankan saat kondisi terpenuhi atau saat peristiwa diterima. Misalnya, saat menggunakan sistem audio untuk mendengarkan radio (sistem dalam status "radio"), menerima hasil stimulus "berikutnya" untuk pindah ke stasiun berikutnya. Ketika sistem berada dalam status "CD", hasil stimulus "berikutnya" untuk pindah ke trek berikutnya. Rangsangan identik memicu tindakan yang berbeda tergantung pada keadaan saat ini.
Dalam beberapa representasi mesin keadaan-hingga, dimungkinkan juga untuk mengaitkan tindakan dengan keadaan:
- tindakan masuk: dilakukan saat memasuki keadaan, dan
- tindakan keluar: dilakukan saat keluar dari keadaan.
Representasi
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/UML_state_machine_Fig5.png/220px-UML_state_machine_Fig5.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/SdlStateMachine.png/220px-SdlStateMachine.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Finite_state_machine_example_with_comments.svg/220px-Finite_state_machine_example_with_comments.svg.png)
Keadaan/Table Acara
Beberapa tipe tabel state transisi digunakan. Representasi yang paling umum ditunjukkan di bawah ini: kombinasi keadaan saat ini (misalnya B) dan masukan (misalnya Y) menunjukkan keadaan berikutnya (misalnya C). Informasi tindakan lengkap tidak langsung dijelaskan dalam tabel dan hanya dapat ditambahkan menggunakan catatan kaki. Definisi FSM termasuk informasi tindakan penuh dimungkinkan menggunakan tabel state (lihat juga FSM virtual).
Keadaan sekarang Masukan
|
Keadaan A | Keadaan B | Keadaan C |
---|---|---|---|
Masukan X | ... | ... | ... |
Masukan Y | ... | Keadaan C | ... |
Masukan Z | ... | ... | ... |
UML mesin keadaan
Unified Modeling Language memiliki notasi untuk mendeskripsikan mesin state. Mesin state UML mengatasi keterbatasan FSM tradisional tetap mempertahankan manfaat utamanya. Mesin keadaan UML memperkenalkan konsep baru dengan state bertingkat hierarki dan wilayah ortogonal, sambil memperluas gagasan tindakan. Mesin state UML memiliki karakteristik mesin Mealy dan mesin Moore. Mereka mendukung tindakan yang bergantung pada status sistem dan peristiwa pemicu, seperti di mesin Mealy, serta tindakan masuk dan keluar, yang terkait dengan keadaan, bukan transisi, seperti di mesin Moore.
SDL mesin keadaan
Spesifikasi dan Deskripsi Bahasa adalah sebuah standar dari ITU yang menyertakan simbol grafis untuk menggambarkan tindakan dalam transisi:
- mengirim acara
- menerima sebuah acara
- mulai pengatur waktu
- batalkan pengatur waktu
- mulai mesin keadaan bersamaan dengan lainnya
- keputusan
SDL menyematkan tipe data dasar yang disebut "Tipe Data Abstrak", bahasa tindakan, dan semantik eksekusi untuk membuat mesin status hingga dapat dieksekusi.
Diagram keadaan lainnya
Ada banyak varian untuk mewakili FSM seperti yang ditunjukkan pada gambar 3.
Pemakaian
Selain penggunaannya dalam pemodelan sistem reaktif yang disajikan di sini, FSM penting di berbagai bidang, termasuk teknik kelistrikan, linguistik, ilmu komputer, filsafat, biologi, matematika, pemrograman video game, dan logika. FSM adalah sebuah kelas dari automata yang mempelajari dalam teori automata dan teori komputasi. Dalam ilmu komputer, FSM banyak digunakan dalam pemodelan perilaku aplikasi, desain sistem digital perangkat keras, rekayasa perangkat lunak, kompiler, protokol jaringan, dan studi komputasi dan bahasa.
Klasifikasi
Mesin keadaan-terbatas dapat dibagi lagi menjadi akseptor, pengklasifikasi, transduser, dan pengurut.[6]
Akseptor
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/220px-Fsm_parsing_word_nice.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/220px-DFAexample.svg.png)
Akseptor (juga disebut detektor atau pengenal) menghasilkan keluaran biner, yang menunjukkan apakah masukan yang diterima diterima atau tidak. Setiap negara bagian penerima adalah menerima atau tidak menerima. Setelah semua masukan diterima, jika keadaan saat ini adalah keadaan menerima, masukan diterima; jika tidak maka ditolak. Sebagai aturan, input adalah urutan simbol (karakter); tindakan tidak digunakan. Status awal juga bisa menjadi status menerima, dalam hal ini penerima menerima string kosong. Contoh pada gambar 4 menunjukkan akseptor yang menerima string "nice". Dalam akseptor ini, satu-satunya status penerima adalah negara bagian 7.
Sekumpulan rangkaian simbol (mungkin tak terbatas), disebut bahasa formal, adalah bahasa biasa jika ada beberapa akseptor yang menerima himpunan itu dengan tepat. Misalnya, himpunan string biner dengan bilangan nol genap adalah bahasa biasa (lihat Gambar 5), sedangkan himpunan semua string yang panjangnya bilangan prima bukan.[7]
Akseptor juga dapat dijelaskan sebagai mendefinisikan bahasa yang akan berisi setiap string yang diterima oleh penerima tetapi tidak ada satupun string yang ditolak; bahasa itu diterima oleh akseptor. Menurut definisi, bahasa yang diterima oleh akseptor adalah bahasa biasa.
Masalah menentukan bahasa yang diterima oleh akseptor tertentu adalah turunan dari masalah jalur aljabar — itu sendiri merupakan generalisasi dari masalah jalur terpendek ke grafik dengan tepi yang diberi bobot oleh elemen semiring (sewenang-wenang).[8][20]
Contoh dari status menerima muncul pada Gambar 5: deterministic finite automaton (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0.
S1 (yang juga merupakan status awal) menunjukkan status di mana bilangan genap 0 telah dimasukkan. Oleh karena itu S1 merupakan negara penerima. Akseptor ini akan selesai dalam status terima, jika string biner berisi bilangan genap 0 (termasuk string biner apa pun yang tidak berisi 0). Contoh string yang diterima oleh akseptor ini adalah ε (string kosong), 1, 11, 11 ..., 00, 010, 1010, 10110, dll.
Pengklasifikasi
Pengklasifikasi adalah generalisasi akseptor yang menghasilkan keluaran n-ary di mana n benar-benar lebih besar dari dua.
Transduser
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Fsm_Moore_model_door_control.svg/220px-Fsm_Moore_model_door_control.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Fsm_mealy_model_door_control.svg/220px-Fsm_mealy_model_door_control.svg.png)
Transduser Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang linguistik komputasi.
Dalam aplikasi kontrol, ada dua jenis yang dibedakan yaitu:
FSM hanya menggunakan tindakan entri, yaitu, keluaran hanya bergantung pada status. Keunggulan model Moore adalah penyederhanaan tingkah laku. Pertimbangkan pintu lift. Mesin negara mengenali dua perintah: "command_open" dan "command_close", yang memicu perubahan status. Tindakan entri (E :) dalam status "Membuka" memulai mesin membuka pintu, tindakan entri dalam status "Menutup" memulai mesin ke arah lain untuk menutup pintu. Menyatakan "Terbuka" dan "Tertutup" menghentikan motor saat dibuka atau ditutup penuh. Mereka memberi sinyal ke dunia luar (mis., Ke mesin keadaan lain) ke dalam situasi: "pintu terbuka" atau "pintu ditutup".
FSM hanya menggunakan tindakan entri, yaitu sebuah keluaran hanya bergantung pada status. Keunggulan model Moore adalah penyederhanaan tingkah laku mesin. Pertimbangkan pintu lift. Mesin state mengenali dua perintah: "command_open" dan "command_close", yang memicu perubahan state. Tindakan entri (E :) dalam status "Membuka" memulai mesin membuka pintu, tindakan entri dalam status "Menutup" memulai mesin ke arah lain untuk menutup pintu. Menyatakan "Terbuka" dan "Tertutup" menghentikan mesin saat dibuka atau ditutup penuh. Mereka memberi sinyal ke dunia luar (mis., Ke mesin state lain) ke dalam situasi: "pintu terbuka" atau "pintu ditutup".
Sequencer
Sequencer (juga disebut generator) adalah subkelas akseptor dan transduser yang memiliki alfabet masukan satu huruf. Mereka hanya menghasilkan satu urutan yang dapat dilihat sebagai urutan keluaran akseptor atau keluaran transduser.[6]
Determinisme
Perbedaan lebih lanjut adalah antara automata deterministik (DFA) dan non-deterministik (NFA, GNFA). Dalam robot deterministik, setiap negara bagian memiliki tepat masing masing satu transisi untuk setiap masukan yang mungkin. Dalam robot non-deterministik, masukan dapat mengarah ke satu, lebih dari satu, atau tidak ada transisi untuk status tertentu. Algoritma konstruksi powerset dapat mengubah robot non-deterministik apa pun menjadi robot deterministik (biasanya lebih kompleks) dengan fungsionalitas yang identik.
FSM dengan hanya satu keadaan disebut "FSM kombinatorial". Ini hanya memungkinkan tindakan setelah transisi ke suatu keadaan. Konsep ini berguna dalam kasus-kasus di mana sejumlah mesin keadaan-hingga diperlukan untuk bekerja sama, dan ketika lebih mudah untuk mempertimbangkan bagian kombinatorial murni sebagai bentuk FSM agar sesuai dengan alat desain.[10]
Alternatif semantik
Di Dalam kumpulan semantik ada yang lain yang tersedia untuk merepresentasikan mesin dengan state. Misalnya, ada alat untuk memodelkan dan mendesain logika untuk pengontrol tertanam. Mereka menggabungkan mesin state hierarkis (yang biasanya memiliki lebih dari satu keadaan saat ini), grafik aliran, dan tabel kebenaran ke dalam satu bahasa, menghasilkan formalisme dan himpunan semantik yang berbeda.[11] Bagan ini dapat menjadi seperti mesin state asli Harel,[12] mendukung keadaan bertingkat secara hierarkis, daerah ortogonal, tindakan keadaan, dan tindakan transisi.[13]
Model Matematika
Sesuai dengan klasifikasi umum, definisi formal berikut ditemukan.
FSM deterministik atau akseptor FSM deterministik adalah kuintupel , di mana:
- adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);
- adalah yang digunakan sebagai alfabet himpunan status tak-kosong berhingga;
- adalah yang digunakan sebagai alfabet state awal, elemen dari ;
- adalah yang digunakan sebagai alfabet fungsi transisi-state: : (dalam robot berhingga non deterministik itu akan menjadi , i.e. akan mengembalikan satu set status);
- adalah yang digunakan sebagai alfabet himpunan state akhir, himpunan bagian (mungkin kosong) dari .
Untuk FSM deterministik dan non-deterministik, penggunaan adalah fungsi parsial, yaitu <math>\delta(s, x)</math> tidak harus ditentukan untuk setiap kombinasi dari dan . Jika FSM dalam keadaan , simbol berikutnya adalah dan tidak ditentukan, maka dapat mengumumkan kesalahan tersebut yaitu menolak input. Ini berguna dalam definisi mesin state umum, tetapi kurang berguna saat mengubah mesin. Beberapa algoritma dalam bentuk defaultnya mungkin memerlukan fungsi total.
FSM memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. Artinya, setiap bahasa formal yang diterima oleh FSM diterima oleh jenis mesin Turing yang dibatasi, dan sebaliknya.
Transduser FSM adalah sextuple , dimana:
- adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);
- adalah yang digunakan sebagai alfabet keluaran (kumpulan simbol tak kosong yang terbatas);
- adalah yang digunakan sebagai himpunan status tak-kosong berhingga;
- adalah yang digunakan sebagai state awal, elemen dari ;
- adalah yang digunakan sebagai fungsi transisi-keadaan: ;
- adalah yang digunakan sebagai fungsi keluaran.
Jika fungsi keluaran bergantung dari status dan simbol masukan () definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan () definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai mesin Moore. FSM tanpa fungsi keluaran sama sekali dikenal sebagai semi-otomatis atau sistem sistem transisi.
Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, , maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.[14]
Optimisasi
Mengoptimalkan FSM berarti menemukan mesin dengan jumlah status minimum yang menjalankan fungsi yang sama. Algoritma tercepat yang diketahui melakukan ini adalah algoritma minimisasi Hopcroft.[15][16] Teknik lain ini termasuk menggunakan tabel implikasi, atau prosedur pengurangan Moore. Selain itu, FSA asiklik dapat diminimalkan dalam waktu linier.[17]
Implementasi
Aplikasi perangkat keras
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/76/4_bit_counter.svg/220px-4_bit_counter.svg.png)
Dalam sirkuit digital, FSM dapat dibangun menggunakan perangkat logika yang dapat diprogram, pengontrol logika yang dapat diprogram, gerbang logika dan flip flop atau relay. Lebih khusus lagi, implementasi perangkat keras memerlukan register untuk menyimpan variabel status, kombinasional blok logika yang menentukan transisi status, dan blok logika kombinasional kedua yang menentukan keluaran FSM. Salah satu implementasi perangkat keras klasik adalah Richards Controller.
Dalam mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.[18][21]
Melalui pengkodean status untuk mesin dengan status daya rendah dapat dioptimalkan untuk meminimalkan konsumsi daya.
Aplikasi software
Konsep berikut biasanya digunakan untuk membangun aplikasi perangkat lunak dengan mesin Keadaan-terbatas:
- Pemrograman berbasis automata
- Mesin finite-state yang digerakkan oleh peristiwa
- Mesin virtual finite-state
- Pola desain state
Mesin dan kompiler Keadaan-terbatas
Automata terbatas sering digunakan di frontend kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, penganalisis leksikal membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.[22]
Lihat Juga
- Abstract state machines (ASM)
- Artificial intelligence (AI)
- Abstract State Machine Language (AsmL)
- Behavior model
- Communicating finite-state machine
- Control system
- Control table
- Decision tables
- DEVS: Discrete Event System Specification
- Extended finite-state machine (EFSM)
- Finite-state machine with datapath
- Hidden Markov model
- Homing sequence
- Low-power FSM synthesis
- Petri net
- Pushdown automaton
- Quantum finite automata (QFA)
- Recognizable language
- SCXML
- Semiautomaton
- Semigroup action
- Sequential logic
- Specification and Description Language
- State diagram
- State pattern
- Synchronizing sequence
- Transformation monoid
- Transition monoid
- Transition system
- Tree automaton
- Turing machine
- UML state machine
- Unique input/output sequence (UIO)
Referensi
- ^ a b Wang, Jiacun (2019). Formal Methods in Computer Science. CRC Press. hlm. 34. ISBN 978-1-4987-7532-8.
- ^ a b "Finite State Machines – Brilliant Math & Science Wiki". brilliant.org. Diakses tanggal 14 April 2018.
- ^ a b Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). Encyclopedia of Computer Science and Technology. 25. USA: CRC Press. hlm. 73. ISBN 978-0-8247-2275-3.
- ^ a b c d Koshy, Thomas (2004). Discrete Mathematics With Applications. Academic Press. hlm. 762. ISBN 978-0-12-421180-3.
- ^ a b Wright, David R. (2005). "Finite State Machines" (PDF). CSC215 Class Notes. David R. Wright website, N. Carolina State Univ. Diarsipkan dari versi asli (PDF) tanggal 27 March 2014. Diakses tanggal 14 July 2012.
- ^ a b c d Keller, Robert M. (2001). "Classifiers, Acceptors, Transducers, and Sequencers" (PDF). Computer Science: Abstraction to Implementation (PDF). Harvey Mudd College. hlm. 480.
- ^ a b Hopcroft, John E. (1979). Introduction to automata theory, languages, and computation. Jeffrey D. Ullman. Reading, Mass.: Addison-Wesley. ISBN 0-201-02988-X. OCLC 4549363.
- ^ a b Pouly, Marc (2011). Generic Inference : a Unifying Theory for Automated Reasoning. Jürg Kohlas. Hoboken, N.J.: Wiley. ISBN 978-1-118-01087-7. OCLC 757511533.
- ^ "inta, 08 ART8.pdf". dx.doi.org. Diakses tanggal 2021-03-21.
- ^ a b Brutscheck, M.; Berger, S.; Franke, M.; Schwarzbacher, A.T.; Becker, S. (2008). "Structural division procedure for efficient IC analysis". IET Irish Signals and Systems Conference (ISSC 2008). IEE. doi:10.1049/cp:20080632. ISBN 978-0-86341-931-7.
- ^ a b Hamon, Grégoire (2005). "A denotational semantics for stateflow". Proceedings of the 5th ACM international conference on Embedded software - EMSOFT '05. New York, New York, USA: ACM Press. doi:10.1145/1086228.1086260. ISBN 1-59593-091-4.
- ^ a b Harel, David (1987-06). "Statecharts: a visual formalism for complex systems". Science of Computer Programming. 8 (3): 231–274. doi:10.1016/0167-6423(87)90035-9. ISSN 0167-6423.
- ^ a b Alur, Rajeev; Kanade, Aditya; Ramesh, S.; Shashidhar, K. C. (2008). "Symbolic analysis for improving simulation coverage of Simulink/Stateflow models". Proceedings of the 7th ACM international conference on Embedded software - EMSOFT '08. New York, New York, USA: ACM Press. doi:10.1145/1450058.1450071. ISBN 978-1-60558-468-3.
- ^ a b Anderson, James A. (2006). Automata theory with modern applications. Thomas J. Head. Cambridge: Cambridge University Press. ISBN 978-0-511-64856-4. OCLC 607557660.
- ^ a b Hopcroft, John (1971). Theory of Machines and Computations. Elsevier. hlm. 189–196. ISBN 978-0-12-417750-5.
- ^ a b Almeida, André; Almeida, Marco; Alves, José; Moreira, Nelma; Reis, Rogério (2009). Implementation and Application of Automata. Berlin, Heidelberg: Springer Berlin Heidelberg. hlm. 65–74. ISBN 978-3-642-02978-3.
- ^ a b Revuz, Dominique (1992-01). "Minimisation of acyclic deterministic automata in linear time". Theoretical Computer Science (dalam bahasa Inggris). 92 (1): 181–189. doi:10.1016/0304-3975(92)90142-3.
- ^ a b Kaeslin, Hubert (2008). "Mealy, Moore, Medvedev-type and combinatorial output bits". Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication. Cambridge University Press. hlm. 787. ISBN 978-0-521-88267-5.
- ^ Slides Diarsipkan 18 January 2017 di Wayback Machine., Synchronous Finite State Machines; Design and Behaviour, University of Applied Sciences Hamburg, p.18
- ^ "inta, 08 ART8.pdf". dx.doi.org. Diakses tanggal 2021-03-21.
- ^ Slides Diarsipkan 18 January 2017 di Wayback Machine., Synchronous Finite State Machines; Design and Behaviour, University of Applied Sciences Hamburg, p.18
- ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools (edisi ke-1st). Addison-Wesley. ISBN 978-0-201-10088-4.
Bacaan Lebih lanjut
Umum
- Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
- Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
- ITU-T, Recommendation Z.100 Specification and Description Language (SDL)
- Samek, M., Practical Statecharts in C/C++, CMP Books, 2002, ISBN 1-57820-110-1.
- Samek, M., Practical UML Statecharts in C/C++, 2nd Edition, Newnes, 2008, ISBN 0-7506-8706-1.
- Gardner, T., Advanced State Management Diarsipkan 2008-11-19 di Wayback Machine., 2007
- Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
- Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
- Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
- Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
- Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
- Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
- Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.
FSM (teori automata) dalam ilmu komputer teoretis
- Arbib, Michael A. (1969). Theories of Abstract Automata (edisi ke-1st). Englewood Cliffs, N.J.: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
- Bobrow, Leonard S.; Arbib, Michael A. (1974). Discrete Mathematics: Applied Algebra for Computer and Information Science
(edisi ke-1st). Philadelphia: W. B. Saunders Company, Inc. ISBN 978-0-7216-1768-8.
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic
(edisi ke-3rd). Cambridge, England: Cambridge University Press. ISBN 978-0-521-20402-6.
- Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
- Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (edisi ke-2nd). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
- Hopcroft, John; Ullman, Jeffrey (1979). Introduction to Automata Theory, Languages, and Computation (edisi ke-1st). Reading Mass: Addison-Wesley. ISBN 978-0-201-02988-8.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (edisi ke-2nd). Reading Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
- Hopkin, David; Moss, Barbara (1976). Automata. New York: Elsevier North-Holland. ISBN 978-0-444-00249-5.
- Kozen, Dexter C. (1997). Automata and Computability (edisi ke-1st). New York: Springer-Verlag. ISBN 978-0-387-94907-9.
- Lewis, Harry R.; Papadimitriou, Christos H. (1998). Elements of the Theory of Computation (edisi ke-2nd). Upper Saddle River, New Jersey: Prentice-Hall. ISBN 978-0-13-262478-7.
- Linz, Peter (2006). Formal Languages and Automata (edisi ke-4th). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3798-6.
- Minsky, Marvin (1967). Computation: Finite and Infinite Machines
(edisi ke-1st). New Jersey: Prentice-Hall.
- Papadimitriou, Christos (1993). Computational Complexity (edisi ke-1st). Addison Wesley. ISBN 978-0-201-53082-7.
- Pippenger, Nicholas (1997). Theories of Computability (edisi ke-1st). Cambridge, England: Cambridge University Press. ISBN 978-0-521-55380-3.
- Rodger, Susan; Finley, Thomas (2006). JFLAP: An Interactive Formal Languages and Automata Package (edisi ke-1st). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3834-1.
- Sipser, Michael (2006). Introduction to the Theory of Computation (edisi ke-2nd). Boston Mass: Thomson Course Technology. ISBN 978-0-534-95097-2.
- Wood, Derick (1987). Theory of Computation (edisi ke-1st). New York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.
Mesin state abstrak dalam ilmu komputer teoritis
- Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms" (PDF). ACM Transactions on Computational Logic. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017
. doi:10.1145/343369.343384.
Pembelajaran mesin menggunakan algoritma finite-state
- Mitchell, Tom M. (1997). Machine Learning (edisi ke-1st). New York: WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.
Rekayasa perangkat keras: minimisasi keadaan dan sintesis rangkaian sekuensial
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Booth, Taylor L. (1971). Digital Networks and Computer Systems (edisi ke-1st). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
- McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits (edisi ke-1st). New York: McGraw-Hill Book Company, Inc. Library of Congress Card Catalog Number 65-17394.
- Hill, Fredrick J.; Peterson, Gerald R. (1965). Introduction to the Theory of Switching Circuits (edisi ke-1st). New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394.
Proses Rantai Finite Markov
- "Kita mungkin menganggap rantai Markov sebagai proses yang bergerak secara berturut-turut melalui sekumpulan keadaan s1, s2, …, sr. … jika dalam keadaan si ia pindah ke perhentian berikutnya untuk menyatakan sj dengan probabilitas pij. Probabilitas ini dapat dipamerkan dalam bentuk matriks transisi "(Kemeny (1959), hal. 384)
Proses rantai-finite Markov juga dikenal sebagai sub-pergeseran tipe terbatas.
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures
(edisi ke-1st). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841. Chapter 6 "Finite Markov Chains".
Tautan Luar
- Finite State Automata di Curlie (dari DMOZ)
- Modeling a Simple AI behavior using a Finite State Machine Example of usage in Video Games
- Free On-Line Dictionary of Computing description of Finite-State Machines
- NIST Dictionary of Algorithms and Data Structures description of Finite-State Machines
- A brief overview of state machine types, comparing theoretical aspects of Mealy, Moore, Harel & UML state machines.
Templat:Bahasa formal dan gramer Templat:Sistem digital
Mesin dan kompiler Keadaan-terbatas
Automata terbatas sering digunakan di bagian depan kompiler bahasa pemrograman. Bagian depan seperti itu dapat terdiri dari beberapa mesin keadaan hingga yang menerapkan penganalisis leksikal dan pengurai. Dimulai dari urutan karakter, penganalisis leksikal membangun urutan token bahasa (seperti kata yang dicadangkan, literal, dan pengenal) tempat parser membangun pohon sintaks. Penganalisis leksikal dan pengurai menangani bagian reguler dan bebas konteks dari tata bahasa bahasa pemrograman.[1]
Lihat Juga
- Abstract state machines (ASM)
- Artificial intelligence (AI)
- Abstract State Machine Language (AsmL)
- Behavior model
- Communicating finite-state machine
- Control system
- Control table
- Decision tables
- DEVS: Discrete Event System Specification
- Extended finite-state machine (EFSM)
- Finite-state machine with datapath
- Hidden Markov model
- Homing sequence
- Low-power FSM synthesis
- Petri net
- Pushdown automaton
- Quantum finite automata (QFA)
- Recognizable language
- SCXML
- Semiautomaton
- Semigroup action
- Sequential logic
- Specification and Description Language
- State diagram
- State pattern
- Synchronizing sequence
- Transformation monoid
- Transition monoid
- Transition system
- Tree automaton
- Turing machine
- UML state machine
- Unique input/output sequence (UIO)
Referensi
- ^ Kesalahan pengutipan: Tag
<ref>
tidak sah; tidak ditemukan teks untuk ref bernamaAddison-Wesley
Bacaan Lebih lanjut
Umum
- Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
- Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
- ITU-T, Recommendation Z.100 Specification and Description Language (SDL)
- Samek, M., Practical Statecharts in C/C++, CMP Books, 2002, ISBN 1-57820-110-1.
- Samek, M., Practical UML Statecharts in C/C++, 2nd Edition, Newnes, 2008, ISBN 0-7506-8706-1.
- Gardner, T., Advanced State Management Diarsipkan 2008-11-19 di Wayback Machine., 2007
- Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
- Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
- Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
- Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
- Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
- Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
- Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.
FSM (teori automata) dalam ilmu komputer teoretis
- Arbib, Michael A. (1969). Theories of Abstract Automata (edisi ke-1st). Englewood Cliffs, N.J.: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
- Bobrow, Leonard S.; Arbib, Michael A. (1974). Discrete Mathematics: Applied Algebra for Computer and Information Science
(edisi ke-1st). Philadelphia: W. B. Saunders Company, Inc. ISBN 978-0-7216-1768-8.
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic
(edisi ke-3rd). Cambridge, England: Cambridge University Press. ISBN 978-0-521-20402-6.
- Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
- Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (edisi ke-2nd). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
- Hopcroft, John; Ullman, Jeffrey (1979). Introduction to Automata Theory, Languages, and Computation (edisi ke-1st). Reading Mass: Addison-Wesley. ISBN 978-0-201-02988-8.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (edisi ke-2nd). Reading Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
- Hopkin, David; Moss, Barbara (1976). Automata. New York: Elsevier North-Holland. ISBN 978-0-444-00249-5.
- Kozen, Dexter C. (1997). Automata and Computability (edisi ke-1st). New York: Springer-Verlag. ISBN 978-0-387-94907-9.
- Lewis, Harry R.; Papadimitriou, Christos H. (1998). Elements of the Theory of Computation (edisi ke-2nd). Upper Saddle River, New Jersey: Prentice-Hall. ISBN 978-0-13-262478-7.
- Linz, Peter (2006). Formal Languages and Automata (edisi ke-4th). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3798-6.
- Minsky, Marvin (1967). Computation: Finite and Infinite Machines
(edisi ke-1st). New Jersey: Prentice-Hall.
- Papadimitriou, Christos (1993). Computational Complexity (edisi ke-1st). Addison Wesley. ISBN 978-0-201-53082-7.
- Pippenger, Nicholas (1997). Theories of Computability (edisi ke-1st). Cambridge, England: Cambridge University Press. ISBN 978-0-521-55380-3.
- Rodger, Susan; Finley, Thomas (2006). JFLAP: An Interactive Formal Languages and Automata Package (edisi ke-1st). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3834-1.
- Sipser, Michael (2006). Introduction to the Theory of Computation (edisi ke-2nd). Boston Mass: Thomson Course Technology. ISBN 978-0-534-95097-2.
- Wood, Derick (1987). Theory of Computation (edisi ke-1st). New York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.
Mesin state abstrak dalam ilmu komputer teoritis
- Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms" (PDF). ACM Transactions on Computational Logic. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017
. doi:10.1145/343369.343384.
Pembelajaran mesin menggunakan algoritma finite-state
- Mitchell, Tom M. (1997). Machine Learning (edisi ke-1st). New York: WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.
Rekayasa perangkat keras: minimisasi keadaan dan sintesis rangkaian sekuensial
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Booth, Taylor L. (1971). Digital Networks and Computer Systems (edisi ke-1st). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
- McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits (edisi ke-1st). New York: McGraw-Hill Book Company, Inc. Library of Congress Card Catalog Number 65-17394.
- Hill, Fredrick J.; Peterson, Gerald R. (1965). Introduction to the Theory of Switching Circuits (edisi ke-1st). New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394.
Proses Rantai Finite Markov
- "Kita mungkin menganggap rantai Markov sebagai proses yang bergerak secara berturut-turut melalui sekumpulan keadaan s1, s2, …, sr. … jika dalam keadaan si ia pindah ke perhentian berikutnya untuk menyatakan sj dengan probabilitas pij. Probabilitas ini dapat dipamerkan dalam bentuk matriks transisi "(Kemeny (1959), hal. 384)
Proses rantai-finite Markov juga dikenal sebagai sub-pergeseran tipe terbatas.
- Booth, Taylor L. (1967). Sequential Machines and Automata Theory (edisi ke-1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
- Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures
(edisi ke-1st). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841. Chapter 6 "Finite Markov Chains".
Tautan Luar
- Finite State Automata di Curlie (dari DMOZ)
- Modeling a Simple AI behavior using a Finite State Machine Example of usage in Video Games
- Free On-Line Dictionary of Computing description of Finite-State Machines
- NIST Dictionary of Algorithms and Data Structures description of Finite-State Machines
- A brief overview of state machine types, comparing theoretical aspects of Mealy, Moore, Harel & UML state machines.