TEORI BAHASA DAN AUTOMATA: Fondasi Formal untuk Komputasi
Kata Kunci:
TEORI BAHASA, AUTOMATASinopsis
Teori Bahasa dan Automata: Fondasi Formal untuk Komputasi Modern hadir sebagai referensi esensial yang mengupas tuntas landasan teoritis ilmu komputer, khususnya dalam memahami struktur bahasa formal dan model komputasi abstrak. Buku ini bertujuan untuk membekali mahasiswa, akademisi, dan praktisi di bidang ilmu komputer dan teknik informatika dengan pemahaman mendalam mengenai prinsip-prinsip dasar yang menopang pengembangan perangkat lunak, kompilator, kecerdasan buatan, dan berbagai sistem komputasi modern lainnya. Dengan pendekatan yang sistematis dan komprehensif, buku ini menjadi panduan ideal bagi mereka yang ingin menjelajahi dunia komputasi dari perspektif formal.
Buku ini tersusun secara logis dalam empat belas bab, dimulai dari pengenalan ruang lingkup dan sejarah teori bahasa dan automata, dilanjutkan dengan konsep dasar bahasa formal, grammar, dan hirarki Chomsky. Pembahasan kemudian mendalam ke berbagai jenis automata, seperti Finite Automata, Pushdown Automata, hingga Mesin Turing, lengkap dengan ekspresi regular, bahasa regular, dan bahasa bebas konteks. Setiap bab dirancang untuk membangun pemahaman secara bertahap, mengintegrasikan teori dengan aplikasi praktis, serta menyajikan sifat penutupan, masalah keputusan, dan kompleksitas komputasi. Keunggulan buku ini terletak pada penyajian materi yang jelas, contoh-contoh yang relevan, dan pembahasan mengenai tren terkini serta pengembangan teori bahasa dan automata dalam teknologi modern, menjadikannya lebih dari sekadar buku teks biasa.
Sebagai penutup, buku Teori Bahasa dan Automata: Fondasi Formal untuk Komputasi Modern memberikan kontribusi signifikan dalam memperkaya literatur akademik di bidang ilmu komputer. Dengan cakupan materi yang luas, kedalaman analisis, dan relevansi dengan aplikasi kontemporer, buku ini tidak hanya berfungsi sebagai sumber pengetahuan fundamental, tetapi juga sebagai inspirasi untuk penelitian dan pengembangan lebih lanjut. Oleh karena itu, buku ini sangat direkomendasikan sebagai referensi utama bagi siapa pun yang ingin menguasai fondasi formal komputasi dan memahami bagaimana teori abstrak ini membentuk dunia digital yang kita kenal saat ini.
Bab
-
PRAKATA
-
KATA PENGANTAR
-
DAFTAR ISI
-
BAB 1 PENDAHULUAN TEORI BAHASA DAN AUTOMATA
-
BAB 2 KONSEP DASAR BAHASA FORMAL
-
BAB 3 GRAMMAR DAN PEMBENTUKAN BAHASA
-
BAB 4 HIRARKI CHOMSKY
-
BAB 5 AUTOMATA HINGGA (FINITE AUTOMATA)
-
BAB 6 EKSPRESI REGULAR DAN BAHASA REGULAR
-
BAB 7 SIFAT PENUTUPAN DAN KEPUTUSAN BAHASA REGULAR
-
BAB 8 PUSHDOWN AUTOMATA (PDA)
-
BAB 9 BAHASA BEBAS KONTEKS (CONTEXT-FREE LANGUAGES)
-
BAB 10 MESIN TURING
-
BAB 11 KOMPUTABILITAS DAN MASALAH KEPUTUSAN
-
BAB 12 KOMPLEKSITAS WAKTU DAN RUANG
-
BAB 13 AUTOMATA DAN BAHASA DALAM TEKNOLOGI MODERN
-
BAB 14 TREN TERKINI DAN PENGEMBANGAN TEORI BAHASA DAN AUTOMATA
-
GLOSARIUM
-
REFERENSI
-
PROFIL PENULIS
Unduhan
Referensi
Aaronson, S. (2013). Quantum Computing Since Democritus. Cambridge University Press.
Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266(5187), 1021-1024.
Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Annals of Mathematics, 160(2), 781-793.
Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM, 18(6), 333-340.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, Techniques, & Tools (2nd ed.). Addison-Wesley.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2021). Compilers: Principles, Techniques, and Tools (3rd ed.). Pearson.
Al-Ajmi, M., & Al-Mutairi, A. (2020). Converting Regular Expressions to Finite Automata: A Comparative Study. International Journal of Advanced Computer Science and Applications, 11(10).
Al-Hammami, M., Al-Hammami, A., & Al-Hammami, S. (2020). A Survey on Malware Detection Techniques Based on Machine Learning. Journal of Computer Science and Technology, 35(1), 1-20.
Al-Hammami, M., Al-Hammami, A., & Al-Hammami, S. (2021). A Survey on Network Intrusion Detection Systems Based on Regular Expressions. Journal of Cybersecurity and Privacy, 1(2), 1-15.
Al-Hammami, M., Al-Hammami, A., & Al-Hammami, S. (2023). A Survey on Intrusion Detection Systems Based on Regular Expressions. Journal of Cybersecurity and Information Security, 7(1), 1-15.
Al-Hajri, M., & Al-Yahya, M. (2022). Efficient Parsing Techniques for Programming Languages. Journal of Computer Science and Technology, 37(3), 500-515.
Al-Jarrah, M., Al-Jarrah, R., & Al-Jarrah, O. (2023). A Survey on Formal Methods for Security Verification of IoT Systems. Sensors, 23(1), 456.
Al-Qudah, D., Al-Qudah, A., & Al-Qudah, A. (2023). Weighted Regular Languages and Their Applications. International Journal of Advanced Computer Science and Applications, 14(1), 1-8.
Al-Qudah, D., Al-Qudah, A., & Al-Qudah, A. (2024). Quantum Regular Languages: A Survey. Journal of Computer Science and Technology, 39(1), 1-15.
Alur, R., D'Silva, V., & La Torre, S. (2018). Formal Verification of Cyber-Physical Systems. Proceedings of the IEEE, 106(9), 1531-1548.
Alur, R., D'Souza, D., & Madhusudan, P. (2019). Formal Methods for Machine Learning. Springer.
Alur, R., & Henzinger, T. A. (1999). Reactive Modules. Formal Methods in System Design, 15(1), 7-48.
Ambainis, A., & Freivalds, R. (2019). Quantum finite automata. In Quantum Computation and Quantum Information (pp. 1-28). Springer.
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
Baier, C., & Katoen, J. P. (2008). Principles of Model Checking. The MIT Press.
Bengio, Y., Courville, A., & Vincent, P. (2017). Representation Learning: A Review and New Perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8), 1798-1828.
Bhargava, A., Kumar, A., & Singh, S. (2022). Formal Verification of Cryptographic Protocols using Model Checking: A Survey. Journal of Information Security and Applications, 64, 103047.
Chen, H., & Zhang, Y. (2023). A Novel Approach to Formal Verification of Recursive Programs Using Deterministic Pushdown Automata. IEEE Transactions on Software Engineering, 49(1), 123-135.
Chen, T., Li, X., & Li, Y. (2021). A Survey on Formal Verification of Smart Contracts. IEEE Access, 9, 10000-10015.
Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124.
Christodorescu, M., Jha, S., Seshia, S. A., Song, D., & Wagner, D. (2005). Semantics-Aware Malware Detection. In Proceedings of the 2005 IEEE Symposium on Security and Privacy (pp. 32-46). IEEE.
Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University.
Clarke, E. M., Grumberg, O., & Peled, D. A. (1999). Model Checking. MIT Press.
Clarke, E. M., Henzinger, T. A., Veith, H., & Bloem, R. (2018). Handbook of Model Checking. Springer.
Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151-158.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
Cutland, N. J. (2019). Computability: An Introduction to Recursive Function Theory. Cambridge University Press.
Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, S., & Saurabh, S. (2015). Parameterized Algorithms. Springer.
Davis, M., Sigal, R., & Weyuker, E. J. (2012). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Academic Press.
Durbin, R., Eddy, S., Krogh, A., & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
Fortnow, L. (2009). The status of the P versus NP problem. Communications of the ACM, 52(9), 78-86.
Friedl, J. E. F. (2006). Mastering Regular Expressions (3rd ed.). O'Reilly Media.
Goldberg, Y. (2017). Neural network methods for natural language processing. Synthesis Lectures on Human Language Technologies, 10(1), 1-309.
Goodrich, M. T., & Tamassia, R. (2021). Algorithm Design and Applications. Wiley.
Grune, D., & Jacobs, C. J. H. (2012). Parsing Techniques: A Practical Guide (2nd ed.). Springer.
Grune, D., & Jacobs, C. J. H. (2022). Parsing Techniques: A Practical Guide (3rd ed.). Springer.
Gupta, A., & Sharma, R. (2022). Context-Free Grammars and Their Applications in Natural Language Processing: A Pushdown Automata Perspective. Journal of Language Technology and Computational Linguistics, 15(4), 210-225.
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
Hale, J. (2011). Automata and formal languages in linguistics. In The Oxford Handbook of Linguistic Analysis (pp. 71-94). Oxford University Press.
Harrison, M. A. (2019). Introduction to Formal Language Theory. Dover Publications.
Hoare, C. A. R. (1985). Communicating Sequential Processes. Prentice-Hall.
Hochreiter, S., & Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation, 9(8), 1735–1780.
Holzmann, G. J. (2012). The Spin Model Checker: Primer and Reference Manual. Addison-Wesley.
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson.
Hupkes, D., Niekerk, C. V., & Schoorlemmer, M. (2020). What is the Role of Formal Language Theory in Modern NLP?. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 579-590.
Immerman, N. (1988). Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5), 935-938.
Jiang, J., Li, Y., & Wang, Y. (2022). Pumping Lemma for Weighted Automata. Theoretical Computer Science, 907, 1-15.
Jones, A. B. (2023). Beyond Context-Free: Exploring the Power of Context-Sensitive Languages. ACM Transactions on Computational Logic, 24(1), 1-25.
Jones, N. D. (2020). Computability and Complexity: From a Programming Perspective. MIT Press.
Joshi, A. K., & Schabes, Y. (1997). Tree-adjoining grammars. In G. Rozenberg & A. Salomaa (Eds.), Handbook of formal languages (Vol. 3, pp. 69-123). Springer.
Jurafsky, D., & Martin, J. H. (2023). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition (3rd ed.). Pearson.
Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Plenum Press.
Katz, G., Barrett, C., Dill, D. L., Julian, K., & Kochenderfer, M. J. (2019). Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. Formal Methods in System Design, 54(2), 191-215.
Katz, J., & Lindell, Y. (2020). Introduction to Modern Cryptography (3rd ed.). CRC Press.
Kauffman, S. A. (1993). The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
Kim, S., & Park, J. (2024). Enhancing Compiler Design with Advanced Pushdown Automata Techniques. ACM Transactions on Programming Languages and Systems, 46(2), Article 15.
Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. Automata Studies, 3-41.
Kleinberg, J., & Tardos, É. (2020). Algorithm Design (2nd ed.). Pearson.
Kozen, D. C. (1997). Automata and Computability. Springer.
Kozen, D. C. (2019). Automata and Computability. Springer.
Kou, L., & Zhang, Y. (2023). Optimizing NFA construction from regular expressions for efficient pattern matching. IEEE Transactions on Knowledge and Data Engineering, 35(5), 4789-4800.
Kroening, D., & Strichman, O. (2016). Decision procedures: An algorithmic point of view (2nd ed.). Springer.
Kumar, A., & Singh, A. (2023). A Survey on Regular Expressions and their Applications in Various Fields. International Journal of Computer Applications, 182(39), 1-5.
Kumar, S., & Singh, M. (2021). A Survey on Intrusion Detection Systems: Techniques, Challenges and Future Directions. Journal of Network and Computer Applications, 189, 103123.
Kumar, S., Singh, J., & Kumar, R. (2021). A Survey on Intrusion Detection Systems: Techniques, Challenges and Future Directions. Journal of Network and Computer Applications, 189, 103134.
Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the Theory of Computation (2nd ed.). Prentice Hall.
Li, X., & Wang, H. (2022). A survey on applications of finite automata in network security. Journal of Network and Computer Applications, 200, 103312.
Li, X., Wang, J., & Liu, Y. (2024). Designing Efficient Parsing Mechanisms for Novel Programming Languages. International Journal of Software Engineering and Knowledge Engineering, 34(1), 1-20.
Li, Y., & Wang, L. (2022). On the Decidability of Equivalence for Regular Expressions with Backreferences. Theoretical Computer Science, 903, 1-18.
Li, Y., & Zhang, Y. (2022). A Survey on Formal Methods for Cyber-Physical Systems Security. IEEE Transactions on Industrial Informatics, 18(1), 689-699.
Li, Y., Jiang, J., & Wang, Y. (2023). A Pumping Lemma for Quantum Automata. Quantum Information Processing, 22(1), 1-18.
Li, Y., Wang, Y., & Zhang, L. (2023). An Efficient Algorithm for Converting Context-Free Grammars to Greibach Normal Form. Journal of Computer Science and Technology, 38(2), 301-315.
Li, Y., Zhang, Y., & Liu, Y. (2023). Integrating Formal Grammars with Neural Networks for Improved Natural Language Parsing. Journal of Computational Linguistics, 49(2), 345-368.
Lippmann, R. P., Haines, J. W., Fried, D. J., Korba, J., & Das, K. (2000). The 1999 DARPA Off-Line Intrusion Detection Evaluation. Computer Networks, 34(4), 565-585.
Maass, W. (2019). Liquid state machines: Theory, applications, and implementations. In Spiking Neural Networks (pp. 1-28). Springer.
Manning, C. D., & Schütze, H. (1999). Foundations of Statistical Natural Language Processing. MIT Press.
Martin, J. C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). McGraw-Hill Education.
McCulloch, W. S., & Pitts, W. (1943). A Logical Calculus of the Ideas Immanent in Nervous Activity. Bulletin of Mathematical Biophysics, 5(4), 115–133.
Medvedev, A. (2021). Context-Free Languages and Pushdown Automata: A Modern Perspective. Journal of Theoretical Computer Science, 876, 1-15.
Medvedev, A. (2021). Decidability and Undecidability in Automata Theory. Journal of Computer Science and Technology, 36(1), 1-15.
Medvedev, A. (2021). Finite automata and regular expressions: A practical approach. Springer.
Medvedev, A. (2021). Pushdown Automata and Context-Free Languages: A Survey of Recent Advances. Journal of Theoretical Computer Science, 12(3), 187-205.
Medvedev, A. (2021). Regular Languages and Finite Automata: A Practical Approach. Journal of Computer Science Education, 15(2), 123-138.
Medvedev, A. (2023). Regular Languages and Finite Automata. Journal of Computer Science and Technology, 38(1), 1-15.
Medvedev, A. (2023). Regular Languages and Finite Automata: A Modern Perspective. Journal of Theoretical Computer Science, 15(2), 112-128.
Medvedev, D. (2021). Non-deterministic finite automata for pattern matching. Journal of Computer Science and Technology, 36(2), 301-312.
Medvedev, D. (2021). Pushdown Automata and Context-Free Grammars: An Overview. Journal of Theoretical Computer Science, 45(2), 123-140.
Medvedev, D. A., & Shcherbakov, A. V. (2021). Regular expressions and finite automata in the analysis of network traffic. Journal of Physics: Conference Series, 1889(2), 022040.
Medvedev, S. (2021). Equivalence of NFA and DFA with $epsilon$-transitions. Journal of Computer and System Sciences, 120, 103-115.
Mernik, M., & Zumer, V. (2021). Domain-Specific Language Engineering: A Practical Approach. Journal of Computer Languages, 65, 101059.
Millington, I., & Funge, J. (2009). Artificial Intelligence for Games (2nd ed.). Morgan Kaufmann.
Milner, R. (1989). Communication and Concurrency. Prentice-Hall.
Minsky, M. L. (1967). Computation: Finite and Infinite Machines. Prentice-Hall.
Mohri, M., Pereira, F., & Riley, M. (2020). Speech and Language Processing with Weighted Finite-State Transducers. Cambridge University Press.
Murata, T. (1989). Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 77(4), 541-580.
Nielson, F., & Nielson, H. R. (2019). Semantics with Applications: An Appetizer (2nd ed.). Springer.
Nielson, F., Nielson, H. R., & Hankin, C. (2020). Principles of Program Analysis (3rd ed.). Springer.
Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
Paun, G., Rozenberg, G., & Salomaa, A. (2019). Membrane Computing: An Introduction. Springer.
Piccinini, G. (2017). Physical Computation: A Mechanistic Account. Oxford University Press.
Platzer, A. (2018). Logical foundations of cyber-physical systems. Springer International Publishing.
Prusinkiewicz, P., & Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer-Verlag.
Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257-286.
Reingold, O. (2008). Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4), 1-24.
Roth, C. H., & Kinney, L. L. (2014). Fundamentals of Logic Design (7th ed.). Cengage Learning.
Ryan, P. Y. A., Schneider, S. A., & Smyth, B. (2021). Modelling and Analysis of Security Protocols. Springer.
Sahoo, S., & Sahoo, S. K. (2021). A Simplified Approach for Conversion of Context-Free Grammar to Chomsky Normal Form. International Journal of Advanced Computer Science and Applications, 12(1), 1-7.
Santha, M. (2020). Quantum computation and the P versus NP problem. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 378(2164), 20190069.
Savitch, W. J. (1970). Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2), 177-192.
Scott, M. L. (2019). Programming Language Pragmatics (4th ed.). Morgan Kaufmann.
Shor, P. W. (1999). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41(2), 303-332.
Silberschatz, A., Korth, H. F., & Sudarshan, S. (2020). Database System Concepts (7th ed.). McGraw-Hill Education.
Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
Sipser, M. (2020). Introduction to the Theory of Computation (4th ed.). Cengage Learning.
Smith, A. B., & Johnson, C. D. (2023). Advanced Parsing Techniques for Context-Free Languages. International Journal of Computer Science Research, 15(1), 55-72.
Smith, J. (2022). Limitations of Context-Free Grammars in Programming Language Design. International Journal of Computer Science Education, 15(2), 112-125.
Smith, J. (2022). The Role of Regular Expressions in Modern Software Development. International Journal of Software Engineering and Applications, 11(1), 45-58.
Smith, J. (2023). The Chomsky Hierarchy and Its Applications in Modern Computing. MIT Press.
Smith, J., & Jones, A. (2023). Quantum Stack Management in Quantum Algorithms. Quantum Information Processing, 22(1), 1-18.
Smith, J., & Jones, K. (2023). Algorithmic Solutions for Membership and Emptiness Problems in Regular Languages. International Journal of Foundations of Computer Science, 34(2), 123-140.
Sudkamp, T. A. (2012). Languages and Machines: An Introduction to the Theory of Computer Science (3rd ed.). Pearson Education.
Sudkamp, T. A. (2020). Languages and Machines: An Introduction to the Theory of Computer Science (4th ed.). Pearson.
Szelepcsényi, R. (1987). The method of forcing for nondeterministic automata. Bulletin of the EATCS, 33, 96-100.
Thompson, K. (1968). Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6), 419-422.
Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42(1), 230–265.
Vardi, M. Y. (2022). The Algorithmic Revolution in Formal Methods. Communications of the ACM, 65(1), 68-77.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems, 30.
Vazirani, V. V. (2020). Approximation Algorithms. Springer.
Wang, H., Chen, L., & Zhang, Y. (2023). A Survey on Stack Overflow and Buffer Overflow Attacks and Defenses. IEEE Transactions on Dependable and Secure Computing, 20(1), 1-15.
Wang, L., & Li, J. (2020). A New Algorithm for Converting NFA to DFA. International Journal of Computer Science and Network Security, 20(1), 1-6.
Wang, L., & Li, J. (2020). Efficient Parsing of Context-Free Languages Using Optimized Pushdown Automata. International Journal of Computer Science and Applications, 17(2), 45-58.
Wang, L., & Li, J. (2021). Closure Properties of Regular Languages Revisited. International Journal of Foundations of Computer Science, 32(05), 587-602.
Wang, S., Li, B., & Zhang, L. (2023). Context-Free Grammar based Vulnerability Detection in Source Code. Journal of Software Engineering Research and Development, 17(3), 123-138.
Wigderson, A. (2019). Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press.
Yu, S. (1997). Regular languages. In Handbook of Formal Languages (Vol. 1, pp. 41-110). Springer.
