Mesin finite-state: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Wagino Bot (bicara | kontrib) |
Add 2 books for Wikipedia:Pemastian (20240209)) #IABot (v2.0.9.5) (GreenC bot |
||
| (4 revisi perantara oleh 3 pengguna tidak ditampilkan) | |||
Baris 1:
{{
{{redirect|Mesin keadaan|mesin keadaan-terbatas|Sistem transisi|Metologi toleransi-kesalahan|Replika mesin keadaan}}
{{redirect|SFSM|perusahaan kereta api Italia|Circumvesuviana}}
Baris 7:
{{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 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.
Baris 65:
=== Keadaan/Table Acara ===
Beberapa tipe [[tabel state transisi
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;"
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.
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]].
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.
Baris 135:
=== Transduser ===
{{Artikel Main|[[Finite-state transduser]]}}
[[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
'''Transduser'''
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]].
Baris 156:
=== 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.<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 ==
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 ==
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 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 ==
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 ==
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 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.
Baris 211:
{{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
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]].<ref name="Belzer2"
== Contoh: pintu putar yang dioperasikan dengan koin ==
[[Berkas:Turnstile_state_machine_colored.svg|jmpl|Diagram state untuk pintu putar]]
[[Berkas:Torniqueterevolution.jpg|jmpl|Pintu Putar]]
Contoh mekanisme sederhana yang dapat dimodelkan oleh mesin state adalah [[pintu putar]].<ref name="Koshy2"
Dianggap sebagai mesin state, pintu putar memiliki dua kemungkinan status: Terkunci dan Tidak Terkunci.<ref name="Koshy2" /> 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.
Baris 269:
=== Keadaan/Table Acara ===
Beberapa tipe [[tabel state transisi
{| class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;"
Baris 316:
== Klasifikasi ==
Mesin keadaan-terbatas dapat dibagi lagi menjadi akseptor, pengklasifikasi, transduser, dan pengurut.<ref name="Keller2001"
=== Akseptor ===
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.
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
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
Contoh dari status menerima muncul pada Gambar 5: [[deterministic finite automaton]] (DFA) yang mendeteksi apakah string input biner berisi bilangan genap 0.
Baris 339:
=== Transduser ===
{{Artikel Main|[[Finite-state transduser]]}}
[[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
'''Transduser'''
Transduser menghasilkan keluaran berdasarkan masukan yang diberikan dan atau keadaan menggunakan tindakan. Mereka digunakan untuk aplikasi kontrol dan di bidang [[linguistik komputasi]].
Baris 360:
=== 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.<ref
== 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
== Model Matematika ==
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 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
== 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
== Implementasi ==
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 mesin Medvedev, output terhubung langsung ke keadaan flip-flop meminimalkan waktu tunda antara flip-flop dan output.<ref
Melalui [[pengkodean status untuk mesin dengan status daya rendah]] dapat dioptimalkan untuk meminimalkan konsumsi daya.
Baris 417:
=== 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 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 ==
Baris 467 ⟶ 466:
* Samek, M., [http://www.state-machine.com/psicc/index.php ''Practical Statecharts in C/C++''], CMP Books, 2002, {{ISBN|1-57820-110-1}}.
* Samek, M., [http://www.state-machine.com/psicc2/index.php ''Practical UML Statecharts in C/C++, 2nd Edition''], Newnes, 2008, {{ISBN|0-7506-8706-1}}.
* Gardner, T., [http://www.troyworks.com/cogs/ ''Advanced State Management''] {{Webarchive|url=https://web.archive.org/web/20081119071252/http://www.troyworks.com/cogs/ |date=2008-11-19 }}, 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}}
Baris 485 ⟶ 484:
* {{cite book|last1=Davis|first1=Martin|last2=Sigal|first2=Ron|last3=Weyuker|first3=Elaine J.|year=1994|title=Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science|location=San Diego|publisher=Academic Press, Harcourt, Brace & Company|isbn=978-0-12-206382-4|edition=2nd}}
* {{cite book|last1=Hopcroft|first1=John|last2=Ullman|first2=Jeffrey|year=1979|title=Introduction to Automata Theory, Languages, and Computation|title-link=Introduction to Automata Theory, Languages, and Computation|location=Reading Mass|publisher=Addison-Wesley|isbn=978-0-201-02988-8|edition=1st}}
* {{cite book|last1=Hopcroft|first1=John E.|last2=Motwani|first2=Rajeev|last3=Ullman|first3=Jeffrey D.|year=2001|title=Introduction to Automata Theory, Languages, and Computation|url=https://archive.org/details/trent_0116404725818|location=Reading Mass|publisher=Addison-Wesley|isbn=978-0-201-44124-6|edition=2nd}}
* {{cite book|last1=Hopkin|first1=David|last2=Moss|first2=Barbara|year=1976|title=Automata|location=New York|publisher=Elsevier North-Holland|isbn=978-0-444-00249-5}}
* {{cite book|last=Kozen|first=Dexter C.|year=1997|title=Automata and Computability|url=https://archive.org/details/automatacomputab0000koze|location=New York|publisher=Springer-Verlag|isbn=978-0-387-94907-9|edition=1st}}
* {{cite book|last1=Lewis|first1=Harry R.|last2=Papadimitriou|first2=Christos H.|year=1998|title=Elements of the Theory of Computation|url=https://archive.org/details/elementsoftheory0000lewi_n0x1|location=Upper Saddle River, New Jersey|publisher=Prentice-Hall|isbn=978-0-13-262478-7|edition=2nd|author-link=Harry R. Lewis|author2-link=Christos H. Papadimitriou}}
* {{cite book|last=Linz|first=Peter|year=2006|title=Formal Languages and Automata|url=https://archive.org/details/introductiontofo0004linz|location=Sudbury, MA|publisher=Jones and Bartlett|isbn=978-0-7637-3798-6|edition=4th}}
* {{cite book|last=Minsky|first=Marvin|year=1967|url=https://archive.org/details/computationfinit0000mins|title=Computation: Finite and Infinite Machines|location=New Jersey|publisher=Prentice-Hall|edition=1st|url-access=registration}}
Baris 532 ⟶ 531:
{{Bahasa formal dan gramer}}
{{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.<ref
== Lihat Juga ==
Baris 586 ⟶ 582:
* Samek, M., [http://www.state-machine.com/psicc/index.php ''Practical Statecharts in C/C++''], CMP Books, 2002, {{ISBN|1-57820-110-1}}.
* Samek, M., [http://www.state-machine.com/psicc2/index.php ''Practical UML Statecharts in C/C++, 2nd Edition''], Newnes, 2008, {{ISBN|0-7506-8706-1}}.
* Gardner, T., [http://www.troyworks.com/cogs/ ''Advanced State Management''] {{Webarchive|url=https://web.archive.org/web/20081119071252/http://www.troyworks.com/cogs/ |date=2008-11-19 }}, 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}}
Baris 604 ⟶ 600:
* {{cite book|last1=Davis|first1=Martin|last2=Sigal|first2=Ron|last3=Weyuker|first3=Elaine J.|year=1994|title=Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science|location=San Diego|publisher=Academic Press, Harcourt, Brace & Company|isbn=978-0-12-206382-4|edition=2nd}}
* {{cite book|last1=Hopcroft|first1=John|last2=Ullman|first2=Jeffrey|year=1979|title=Introduction to Automata Theory, Languages, and Computation|title-link=Introduction to Automata Theory, Languages, and Computation|location=Reading Mass|publisher=Addison-Wesley|isbn=978-0-201-02988-8|edition=1st}}
* {{cite book|last1=Hopcroft|first1=John E.|last2=Motwani|first2=Rajeev|last3=Ullman|first3=Jeffrey D.|year=2001|title=Introduction to Automata Theory, Languages, and Computation|url=https://archive.org/details/trent_0116404725818|location=Reading Mass|publisher=Addison-Wesley|isbn=978-0-201-44124-6|edition=2nd}}
* {{cite book|last1=Hopkin|first1=David|last2=Moss|first2=Barbara|year=1976|title=Automata|location=New York|publisher=Elsevier North-Holland|isbn=978-0-444-00249-5}}
* {{cite book|last=Kozen|first=Dexter C.|year=1997|title=Automata and Computability|url=https://archive.org/details/automatacomputab0000koze|location=New York|publisher=Springer-Verlag|isbn=978-0-387-94907-9|edition=1st}}
* {{cite book|last1=Lewis|first1=Harry R.|last2=Papadimitriou|first2=Christos H.|year=1998|title=Elements of the Theory of Computation|url=https://archive.org/details/elementsoftheory0000lewi_n0x1|location=Upper Saddle River, New Jersey|publisher=Prentice-Hall|isbn=978-0-13-262478-7|edition=2nd|author-link=Harry R. Lewis|author2-link=Christos H. Papadimitriou}}
* {{cite book|last=Linz|first=Peter|year=2006|title=Formal Languages and Automata|url=https://archive.org/details/introductiontofo0004linz|location=Sudbury, MA|publisher=Jones and Bartlett|isbn=978-0-7637-3798-6|edition=4th}}
* {{cite book|last=Minsky|first=Marvin|year=1967|url=https://archive.org/details/computationfinit0000mins|title=Computation: Finite and Infinite Machines|location=New Jersey|publisher=Prentice-Hall|edition=1st|url-access=registration}}
| |||