کاربردهایی از آتوماتای متناهی قطعی و غیرقطعی

نوع مقاله : مقاله پژوهشی

نویسنده

گروه ریاضی، دانشکده علوم پایه، دانشگاه شهید مدنی آذربایجان

چکیده

مباحث مربوط به زبان‌های صوری و مدل‌های مناسب برای آن‌ها، از مفاهیم پایه و اساسی در رشته علوم کامپیوتر است. از ساده‌ترین مدل‌های محاسبه، آتوماتای متناهی هستند. دلیل سادگی این نوع ماشین‌ها این است که حافظه کمکی در آن‌ها وجود ندارد؛ با وجود این، بسیاری از مسائل را می‌توان با استفاده از آتوماتای متناهی حل کرد. در این مقاله مفهوم آتوماتون متناهی قطعی و غیرقطعی معرفی می‌شود. سپس از آتوماتای متناهی در جستجوی متن برای یک نمونه خاص استفاده می‌شود. هم‌چنین روند خرید اینترنتی با استفاده از آن مدل‌سازی می‌شود.

کلیدواژه‌ها


[1] M. Crochemore and T. Lecroq, Pattern matching and textcompression algorithms, The computer science and engineering Handbook, A. B Tucker, Jr. ed., CRC Press, Boca Raton, 2003.
[2] K. Culik II and J. Kari, Image compression using weighted finite automata, Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 711, Springer, Berlin, (1993) 392–402.
[3] D. Ding-Zhu and K. Ker-I., Problem Solving in Automata, Languages and Complexity, 1st edition, New York, Wiley-
Interscience, 2001.
[4] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
[5] D. A. Huffman, The synthesis of sequential switching circuits, J. Franklin Inst., 257 (1954) 275–303.
[6] P. Linz, Introduction to Formal Languages and Automata, 5th edition, Canada, Jones Bartlett Learning, 2011.
[7] J. C. Martin, Introduction to Languages and The Theory of Computation, 4th edition, New York, McGraw-Hill Education, 2010.
[8] G. Navarro and R. Baeza- Yates, Improving an Algorithm for Approximate Pattern Matching, Algorithmica, 30 (2001) 473–502.
[9] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop, 3 (1959) 114–125.
10] M. Sipser, Introduction to the Theory of Computation, 3rd edition, United States, Cengage Learning, 2012.