Unit 3: Finite State Machines
Finite state machines (FSM), also called finite state automata (FSA), are conceptual models for recognizing, parsing, and generating strings in a formal language. An FSM can be used to recognize (i.e., determine) whether a string adheres to the syntax of a language. Moreover, an FSM can be used to build a syntax tree, which shows the derivation (i.e., how the string was constructed) of the string. This unit introduces (or reviews) FSMs, which are covered in detail in other courses (for example, CS202: Discrete Structures).
Completing this unit should take you approximately 6 hours.
3.1: Definitions
Study slides 9 - 33. These slides describe and give examples of regular languages/regular expressions and their corresponding finite state machine.
Study slides 1-5.
3.2: Some Results and Examples of FSAs
Study slides 34 - 76. These slides give results and examples of conversion from a non-deterministic finite state automaton (NFA) to a deterministic finite state automaton (DFA); regular expressions or strings; context free grammars and pushdown automata (PDA); and context sensitive grammars and Turing machines. They also introduce parsing and abstract syntax trees.
Study slides 6 and 7.
3.3: Some Applications of FSA
Study slides 8 to the end. These notes repeat some of the material from section 3.2 and provide additional practice in applying FSAs.
Unit 3 Assessment
Please take this assessment to check your understanding of the materials presented in this unit.
Notes:
- There is no minimum required score to pass this assessment, and your score on this assessment will not factor into your overall course grade.
- This assessment is designed to prepare you for the Final Exam that will determine your course grade. Upon submission of your assessment you will be provided with the correct answers and/or other feedback meant to help in your understanding of the topics being assessed.
- You may attempt this assessment as many times as needed, whenever you would like.