CSC240 Winter 2021 Homework Assignment 9
due Tuesday March 30, 2021
1. Construct a deterministic finite automaton that accepts the language consisting of every string in {0, 1}+ that does not contain the substring 011. For example, 0101 should be accepted by your finite automaton, but λ and 0110 should be rejected.
• Express your finite automaton as a 5 tuple. • Draw your finite automaton.
2. For each state q in your finite automaton, give a regular expression rq that describes the set of strings in {0,1}∗ that take your finite automaton from its initial state to q. Remember that the only symbols you can use in your regular expressions are 0, 1, (, ), ·, +, and ∗.
3. Give a careful proof using induction that your answers for questions 1 and 2 are correct.