Automata Theory and Formal Languages: A Practical Handbook (309,00 руб.)

Стр.3

Стр.4

Стр.5

Стр.6

Стр.7

УДК 519.713:004(075.8) ББК 22.18+32.815 я73 М74 Печатается по решению кафедры Алгебры и дискретной математики института математики, механики и компьютерных наук им. И. И. Воровича Южного федерального университета (протокол № 8 от 09.06.2025) Рецензенты: доктор физико-математических наук, профессор кафедры высшей математики Московского физико-технический институт (МФТИ) В. А. Стукопин; доктор технических наук, заведующий кафедрой Алгебры и дискретной математики ИММиКН ЮФУ Б. Я. Штейнберг Могилевская, Н. С. М74 Automata Theory and Formal Languages: A Practical Handbook : учебное пособие / Н. С. Могилевская ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2025. – 206 с. ISBN 978-5-9275-5065-4 Учебное пособие предназначено для студентов бакалавриата направления 02.03.02 «Фундаментальная информатика и информационные технологии», изучающих курс «Automata Theory and Formal Languages» на английском языке. Издание также будет полезно преподавателям, ведущим практические занятия по данной дисциплине. Пособие содержит ключевые теоретические положения теории автоматов и формальных языков, а также обширный практикум, включающий разобранные примеры, задания для аудиторной работы и задачи для самостоятельного решения. УДК 519.713:004(075.8) ББК 22.18+32.815 я73 ISBN 978-5-9275-5065-4 © Южный федеральный университет, 2025 © Могилевская Н. С., 2025 © Иллюстрации Амрахова А. И., 2025 2

Стр.3

Content Foreword .................................................................................................... 7 Introduction ................................................................................................ 9 1. Symbols, Strings and Languages .................................................... 11 1.1. Alphabet, Strings, Operations over Strings ......................................... 11 1.2. Languages, Operation over Languages ............................................... 15 1.3. Solved Examples .................................................................................. 19 1.4. Class Exercises ..................................................................................... 22 1.5. Exercises for Self-Study ....................................................................... 23 1.6. Self-Assessment Questions .................................................................. 26 2. Formal Grammars ............................................................................ 27 2.1. Definition of Formal Grammar ........................................................... 27 2.2. Classification of Grammars (Chomsky Hierarchy) ............................ 32 2.3. Note on the Relationship Between Grammar and Language ............ 35 2.4. Solved Examples .................................................................................. 38 2.5. Class Exercises ..................................................................................... 42 2.6. Exercises for Self-Study ....................................................................... 44 2.7. Self-Assessment Questions .................................................................. 48 3. Regular Expressions ......................................................................... 49 3.1. Introduction to Regular Expressions ................................................... 49 3.2. Regular Sets and Regular Languages .................................................. 50 3.3. Properties of Regular Expressions ....................................................... 53 3.4. Order of Operations in Regular Expressions. ..................................... 55 3.5. Regular Expression Equations ............................................................. 56 3.6. System of Equations with Regular Coefficients ................................. 58 3

Стр.4

3.7. Regular and Right-Linear Languages ................................................. 61 3.8. Solved Examples .................................................................................. 65 3.9. Class Exercises ..................................................................................... 72 3.10. Exercises for Self-Study ...................................................................... 74 3.11. Self-Assessment Questions ................................................................. 78 4. Finite Automata ................................................................................ 79 4.1. Main Definitions .................................................................................. 80 4.2. Graph of a Finite Automaton ............................................................... 84 4.3. Extending Incomplete DFA to Completely Specified DFA .............. 88 4.4. Equivalence of NFA and DFA ............................................................. 89 4.5. Finite Automaton with ε-Transitions (ε-NFA) ................................... 92 4.6. Equivalence of ε-NFA and DFA ......................................................... 96 4.7. Comparison ε-NFA, NFA and DFA .................................................. 100 4.8. Minimization of Finite Automata ...................................................... 101 4.9. Solved Examples ................................................................................ 118 4.10. Class Exercises ................................................................................... 130 4.11. Exercises for Self-Study .................................................................... 135 4.12. Self-Assessment Questions ............................................................... 142 5. Equivalence of Finite-Automaton, Regular, and Right-Linear Languages ......................................................................................................... 144 5.1. Kleene’s Theorem .............................................................................. 144 5.2. Connection between Right-Linear and Regular Languages ............ 145 5.2.1. From Regular Expression to Right-Linear Grammar ........ 145 5.2.2. From Right-Linear Grammar to Regular Expression ........ 147 5.3. Connection between Regular Expressions and Finite Automata .... 147 5.3.1. Thompson’s Construction: From Regular Expressions to Finite Automata ......................................................................................... 147 4

Стр.5

5.3.2. Algebraic Justification for the Transition from Regular Expressions to Finite Automata ................................................................. 152 5.3.3. State Elimination Method for Converting Finite Automata to Regular Expressions .................................................................................. 155 5.4. Connection between RL Grammars and Finite Automata .............. 158 5.4.1. From Finite Automata to Right-Linear Grammars ............. 159 5.4.2. From Right-Linear Grammars to Finite Automata ............. 160 5.5. The Pumping Lemma for Regular Languages ................................ 164 5.5.1. The Lemma and Its Proof .................................................... 164 5.5.2. How to Use the Pumping Lemma - Proof Template ........... 166 5.6. Solved Examples ............................................................................... 168 5.8. Exercises for Self-Study .................................................................... 175 5.9. Self-Assessment Questions ............................................................... 177 6. Pushdown Automaton ....................................................................... 179 6.1. The Chomsky Hierarchy: Grammars, Languages, and Automata . 179 6.2. Pushdown Automaton: An Informal Overview ............................... 180 6.3. Pushdown Automaton: Formal Definition ....................................... 182 6.4. Graph of a Pushdown Automaton .................................................... 184 6.5. Solved Examples ............................................................................... 186 6.6. Class Exercises .................................................................................. 189 6.7. Exercises for Self-Study .................................................................... 189 6.8. Self-Assessment Questions ............................................................... 189 Appendices.............................................................................................. 191 Appendix A. Course Projects: Building Automata Theory Tools ............. 191 Appendix B. Backus-Naur Form ................................................................. 193 Appendix C. Modeling Character Behavior in Computer Games ............ 194 5

Стр.6

Appendix D. Index of Algorithms ............................................................... 197 Appendix E. Index of Theorems and Lemmas ........................................... 198 Appendix F. Sample Assignments for Written Work .................................. 200 F.1. Word Operations and Grammars ........................................... 200 F.2. Regular Expressions .............................................................. 201 F.3. Basic Definitions and Formulations of Key Results ............. 201 F.4. The Relationship between Finite Automata, Regular Expressions, and Right-Linear Grammars ................................................ 202 F.5. Finite Automata ..................................................................... 203 References ............................................................................................... 205 6

Стр.7