Assignment #1
Due on 9-24-09
- (10 points) Is the function in
Example 0.8 onto? Explain
- (10 points) Is the function in
Example 0.9 onto? Explain
- (10 points) Is the Cartesian
product of two languages a language? Explain
- (15 points) Prove or disprove the
statement that, for any strings z and w on the same alphabet, z is a
substring of w if, and only if, zz is a substring of ww.
- (15 points) Solve exercise 0.10
from page 27
- (17 points) Describe a
deterministic finite automaton with the alphabet that accepts a string
if, and only if, its component letters are in alphabetical order.
- (23 points) Solve exercise 1.4(g)
Assignment #2
Due on 10-06-09
- (16 points)Solve
exercise 1.6(1) page 84
- (16 points)Solve
exercise 1.7(c) page 84
- (16 points)Solve
exercise 1.8(b) page 84
- (20 points)Solve
exercise 1.15page 85
- (16 points)Solve
exercise 1.16(b) page 86
- (16 points)Solve
exercise 1.5(f) page 84
Assignment #3
Due on 10-20-09
Solve
exercises 1.18, 1.19, and 1.21 all parts, answer document, solutions
Assignment #4
Due on 10-27-09
Use
the JFLAP software to
create NFAs and their equivalent DFAs for 5 of the languages
listed in exercise 1.20 of page 86. Submit a report that includes
print-outs of your designs and transformations, samples of
strings in the language and tested used the JFLAP software, and learning
experience.
Solve
exercises 2.4-b (page 128), 2.14 (page 129), 2.19 (page 130), and
2.27-a (page 130)
answer document
Assignment #7
Due on 12-1-09
Solve
exercises 3.1 a,c, and d, 3.4 from page 159, and 3.8 b and c from
page 160
Assignment #8
Due on 12-10-09
- Solve
exercises 3.15 b, c, d, and e,
- Consider the problem of determining whether a NFA and
a regular expression are equivalent. Express this problem as a language
and show that it is decidable. Use indirect method.
- Let A1={<A> | A is a DFA and
L(A)=1110*1 with alphabet={0,1}}. Show that A1 is
decidable. Use indirect method.
|