documentation

COSC 3302 Foundations of Computer Science

Assignment 2

Exercise 1 (Ex. 1, Chapter 2 of [Martin; 2011]). In each part below, draw an FA accepting the

indicated language over {a, b}.

a. The language of all strings containing exactly two a’s.

b. The language of all strings containing at least two a’s.

c. The language of all strings that do not end with ab.

d. The language of all strings that begin or end with aa or bb.

Exercise 2 (Ex. 4, Chapter 2 of [Martin; 2011]). Example 2.7 describes an FA accepting L3, the set of strings in {0, 1}

* that are binary

representations of integers divisible by 3.

Draw a transition diagram for an FA accepting L5, the set of strings in {0, 1}

* that are binary

representations of integers divisible by 5.

Exercise 3. What languages do the following automata accept? Determine the memory

representation (also called encoding) of these automata as either matrix or a class that you would

use in a Java program.

a)

b)

q0

a

b q1

b

q0

a

b q1

b

Exercise 4 (Ex. 10, Chapter 2 of [Martin; 2011]). Let M1 and M2 be the finite automata pictured

below with their accepting languages L1 and L2. Draw the finite automata for L1 ⋃ L2, L1 ⋂ L2, and L1 – L2.

Exercise 5 (Ex. 12, Chapter 2 of [Martin; 2011]).

Exercise 6 (Ex. 17, Chapter 2 of [Martin; 2011]).

Exercise 7 (Ex. 22, Chapter 1 of [Martin; 2011]). Using the pumping lemma, show that the

below languages are not regular:

Exercise 8 (Ex. 38, Chapter 1 of [Martin; 2011]).

Exercise 9 (Ex. 53, Chapter 1 of [Martin; 2011]). For each of the finite automaton pictured

below, use the minimization algorithm described in Section 2.6 and Lecture 2 to find a minimum-

state finite automaton recognizing the same language. (It is possible that the given FA may already

be minimal.)