CS304: Compilers (2018.A.01), Topic: Unit 3: Finite State Machines

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.
- Upon successful completion of this unit, you will be able to:
  
  Define the types of finite state machines (FSMs) used in the compilation process.
  
  Identify the type of language and grammar recognized by each type of FSM.
  
  Explain the use of FSA in the compilation process.
- 3.1: Definitions
  - Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars" URL
    
    Study slides 9 - 33. These slides describe and give examples of regular languages/regular expressions and their corresponding finite state machine.
  - University of California, Berkeley: Paul Hilfinger's "Lexical Analysis, Regular Expressions" URL
    
    Study these slides.
  - University of California, Berkeley: Paul Hilfinger's "FSA" URL
    
    Study slides 1-5.
- 3.2: Some Results and Examples of FSAs
  - Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars" URL
    
    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.
  - University of California, Berkeley: Paul Hilfinger's "FSA" URL
    
    Study slides 6 and 7.
- 3.3: Some Applications of FSA
  - University of California, Berkeley: Paul Hilfinger's "FSA" URL
    
    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
  - Unit 3 Assessment Quiz
    
    Receive a grade
    
    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.

Unit 3: Finite State Machines

3.1: Definitions

3.2: Some Results and Examples of FSAs

3.3: Some Applications of FSA

Unit 3 Assessment