Problem Set 1—Finite Automata

Purpose

This problem set reinforces your understanding of finite automata. In particular, it focuses on deterministic finite automata, nondeterministic finite automata, and their equivalence to each other.

Background

This problem set is based on material in sections 1.1 and 1.2 of our textbook. We discussed, or will discuss, this material in class on January 22, 25, and 27.

Activity

Solve each of the following problems.

Problem 1

Exercise 1.6a in our textbook (give a DFA that recognizes the language over {0,1} containing exactly those strings that begin with a 1 and end with a 0).

Problem 2

Exercise 1.7b in our textbook (give a 5-state NFA that recognizes the language over {0,1} containing exactly those strings that contain the substring 0101).

Problem 3

Exercise 1.16b in our textbook (use the NFA-to-DFA construction to construct a DFA from a certain 3-state NFA; see the textbook for details).

Problem 4

Problem 1.32 in our textbook (show that, given an alphabet of 3-bit symbols, a language that corresponds to binary addition is regular; see the textbook for details).

Problem 5

Phineas Phoole proposes a new kind of finite automaton called a “Phoolish Finite Automaton” (PFA) which is like an NFA except that the transition function maps states and strings to sets of states. If δ(q,w₁w₂…w_n) = {q_i…q_j} then, when the machine is in state q and the next n input symbols are w₁w₂…w_n, the machine consumes those n input symbols and nondeterministically enters states q_i…q_j. Note that n can be any integer greater than or equal to 0, and that the set {q_i…q_j} may be empty.

Show that every language recognized by a PFA is also recognized by some NFA.

(In solving this problem, you are basically proving that the set of languages recognized by PFAs is the same as the set of language recognized by NFAs, since every NFA is a trivial PFA. PFAs as described here are actually a special case of a real thing called a “generalized NFA,” which we will see in a week or so.)

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.