Unit 9 Activities
Time Advisory
This unit should take you 5.5 hours to complete.
- Subunit 9.1: 1 hours
- Subunit 9.2: 1.5 hours
- Assignment 1: 3 hours
Learning Outcomes
Upon successful completion of this unit, you will be able to:- define formal languages using operator precedence and regular expressions;
- construct and analyze finite state automata; and
- relate formal languages and automata.
9.1 Formal Languages
Reading: Saylor Academy's "Formal Languages” (PDF)
Instructions: Read this discussion of grammar and formal languages.
Reading this selection and taking notes should take approximately 15 minutes.
9.1.1 Polish Notation
Reading: Saylor Academy's "Polish Notation” (PDF)
Instructions: Read this discussion of Polish notation for describing expressions.
Reading this selection and taking notes should take approximately 15 minutes.
9.1.2 Languages Defined by Regular Expressions
Reading: Saylor Academy's "Languages Defined by Regular Expressions” (PDF)
Instructions: Read this discussion of languages defined by regular expressions.
Reading this selection and taking notes should take approximately 15 minutes.
9.1.2.1 Order of Precedence Rules
Reading: Saylor Academy's "Order of Precedence Rules” (PDF)
Instructions: Read this discussion of operator precedence.
Reading this selection and taking notes should take approximately 15 minutes.
9.1.2.2 Deciding Whether Regular Expressions Define the Same Language
Reading: Saylor Academy's "Deciding Whether Regular Expressions Define the Same Language” (PDF)
Instructions: Download the linked file for a discussion of operator precedence.
Reading this selection and taking notes should take approximately 15 minutes.
9.2 Finite State Automata
Reading: Saylor Academy's "Finite State Automata” (PDF)
Instructions: Read this discussion on finite state automata.
Reading this selection and taking notes should take approximately 30 minutes.
9.2.1 Automaton and Accepted Language
Reading: Saylor Academy's "Automaton and Accepted Language” (PDF)
Instructions: Read this discussion of regular sets and their acceptance by finite state automata.
Reading this selection and taking notes should take approximately 15 minutes.
9.2.2 Designing a Finite State Automaton
Reading: Saylor Academy's "Designing a Finite State Automaton” (PDF)
Instructions: Read this discussion of hints on designing a finite state automaton to recognize a given regular set.
Reading this selection and taking notes should take approximately 15 minutes.
9.2.3 Showing that a Language Is Not Regular
Not all languages are regular. Because a finite state machine has a finite number of states, it can only remember a finite number of inputs. Consider the set {on 1n for all n >= 0}. Because this set requires a recognizing machine to remember n 0's for any n (so that it can then look for n 1's), the number of states is infinite, i.e. not a finite state machine. Thus, the language is not regular. Hence, one way to show that a language is not regular is to show that the automaton that recognizes it has an infinite number of states.
9.2.4 Simplifying Finite State Automata
Reading: Saylor Academy's "Simplifying Finite State Automata” (PDF)
Instructions: Read this discussion of ways to simplify finite state automata.
Reading this selection and taking notes should take approximately 30 minutes.
9.3 Unit 9: Assignment 1
Assignment: Saylor Academy's "Unit 9 Assignment” (PDF)
Instruction: Please complete this assignment. Then, check your answers against the answer key.
Completing this assignment should take approximately 3 hours.