Homework 2 (due 9/27)
CSC 344/444

This week we talked about decidability (4.1) and the basics of finite state machines (5.1-5.4). We built several machines, including a binary adder (slightly simplified), as described on page 25 of the book. Next week we will finish chapter 5 (5/4-5/8).

Homework is due at the beginning of next class for in-class students and by midnight for OL students.

Submission: you can submit the homework by hardcopy in class or by sending it to me as an email.

1. [Reading Assignment] Read Sections 5.1-5.3 of the book.

2. [Finite State Automaton, 5pt] Install jflap (or use the applet version). Download the mystery finite automaton. What language does it accept?

3. [Deterministic finite automata, 16pt] Build deterministic finite automata for the following languages:

  1. L = {w in {a,b,c}*: if w contains an a, it also contains a b}. Note: the b can be anywhere in the string, not necessarily right after a.
  2. L = {w in {a,b}*: w does not end in aa}.
  3. L = {w in {a,b,c}*: the first and last letter of w are the same}.
  4. L = {w in {a,b,c}*: w does not contain the substring cab}.

Create a test-suite of strings and run your automaton on those strings, and submit a screenshot of your automaton with those test-runs (use the Input/Multiple run feature).

4. [Nondeterministic finite automata, 10pt] Build nondeterministic finite automata for the following languages:

  1. L = {w in {0,1,2,3,4,5,6,7,8,9}*: w contains a substring which represents a natural number divisible by 3}. Hint: a number x is divisible by 3 if the sum of its digits is divisible by 3. 
  2. L = {w in {a,b}*: w contains both the string aba and bab}. Note: the occurrences of the strings may overlap, but they don't have to.

5. [Regular Languages, 5pt] Show that the language {w in {a,b}*: more than half the letters in w are a} is not regular. Hint: use a similar argument as the one we used for the missing letter language.  Assume there is a finite automaton M with n states; show that there are two strings bk and bm, k<m, that leave M in the same state (starting with s, the starting state). Why is that sufficient?

6. [Extra Credit] Prove or disprove: any sequence of three decimal digits contains a non-empty subsequence which represents a number divisible by 3. E.g. 842 contains the subsequence 42 which is divisible by 3.

Marcus Schaefer
Last updated: September 21st, 2010.