CS374: Programming Language Principles - Finite Automata

Activity Goals

The goals of this activity are:
  1. To define a finite state machine
  2. To relate a finite state machine to the grammar definition of a programming language

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Finite Automata

(A+B)*ABAB

Questions

  1. Design a flow chart that reads one character at a time until the sequence ABAB is found.
  2. Using the FSM Designer, draw a finite state machine that accepts the strings in the given by the regular language.
  3. Using the FSM simulator, implement the finite state machine to check and accept the appropriate strings in this language.
  4. Can you determine how many extraneous A and B characters were seen before reaching the accepting state? If not, what additional information would be needed to do so?
  5. How does a finite state machine relate to a regular expression?
  6. What do finite automata have to do with programming languages? Specifically, how can they help us to connect syntax with semantics?
  7. Why would it be difficult to design a finite state machine to accept all strings of A and B such that the number of A and B characters are equal? If it were possible to design such a machine, what would be the corresponding regular expression?

Model 2: SQL SELECT Language Automata

Oracle SQL Flowchart

Questions

  1. What language is described by this automaton?

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.