The most important item on all homework is YOUR NAME! No name, no credit. Staple or clip pages together.
Homework must be submitted when due. You loose 10%, one grade, the first day homework is late. Then 10% more per week, each week homework is late. Max of 50% off. A ZERO really hurts your final points. Do and turn in all homework, even if it is late. Paper or EMail to squire@cs.umbc.edu is acceptable. If I can not read or understand your homework, you do not get credit. Type or print if your handwriting is bad. Homework is always due on a scheduled class day within 15 minutes after the start of the class. If class is canceled then homework is due the next time the class meets.
EMail only plain text! No word processor formats.
You may use a word processor or other software tools and
print the results and turn in paper.
Use the same technique for plain text as is used in this WEB
page. Write out Greek letters, a plus means union in expressions,
a star after an expression is a Kleene star, see Language definitions
Just turn in two columns, column 1 has numbers 1 through 25, column 2 has a letter indicating your choice of the definition that best matches. 1. symbol 2. alphabet 3. string 4. formal language 5. regular language 6. regular expression 7. (0+1)* (00+11) 8. grammar 9. L(M) 10. L(G) 11. CFL 12. r.e. 13. finite automata 14. nondeterministic finite automata 15. pushdown automata 16. Turing machine 17. universal Turing machine 18. Moore machine 19. Mealey machine 20. NFA 21. TM 22. PDA 23. M(G) 24. M(L) 25. CYK Definition a. abbreviation for recursively enumerable b. abbreviation for Nondeterministic Finite Automata c. abbreviation for Context Free Language d. abbreviation for Turing Machine e. abbreviation for Cocke-Younger-Kasami algorithm f. a regular expression g. a machine defined by a grammar h. a machine defined by a language i. a Turing machine that simulates all other Turing machines j. a machine that outputs every time a state is entered k. a machine that outputs based on the input symbol and state l. a machine that uses a tape like a push down stack m. a language defined by a machine n. a language defined by a grammar o. a language representable by a finite automata p. a set of strings q. M = (Q, sigma, delta, q0, F) r. a finite automata with sets in its transition table s. an expression formed by concatenation, union and Kleene star t. uninterpreted mark u. finite set of symbols v. abbreviation for Push Down Automata w. a concatenation of symbols x. G = (V, T, P, S) y. a regular expression with all strings ending in 00 or 11 z. no other answer applies
Remember: A set of strings is a Language. Do Exercise 2.5 a) b) and c), page 48 with the additional requirement to write the regular expressions for each case. For example, the regular expression for 2.5 a) is (0+1)* 00 Do exercise 2.6 a), page 48 with the additional requirement to write the regular expression for this case. Use the same type of "Describe in English" as was used in 2.5
The constructive proofs in sections 2.3 and 2.4 show that every
NFA can be converted to a DFA.
1) Convert the NFA in figure 2.7 on page 21 to an equivalent DFA
M = (Q, sigma, alpha, q0, F)
Q = { ? }
F = { ? }
q0 = ?
sigma = old sigma
alpha = ? transition table ?
2) Convert NFA with epsilon moves figure 2.9 page 25 to a DFA.
M = (Q, sigma, alpha, q0, F)
Q = { ? }
F = { ? }
q0 = ?
sigma = old sigma
alpha = ? transition table ?
Hints and actually partial solutions are in WEB Page link below
or here Selected Lecture Notes, Lecture 4
and figure 2.10 on page 27.
You can draw small circles for diagrams, no state labels needed, but
make it neat so it can be graded.
1) Convert a regular expression to a NFA-epsilon machine (diagram only)
1(0+1)* 0
2) Convert a regular expression to a NFA-epsilon machine (diagram only)
(0+1)* + (a+b)*
3) Convert machine given by delta transition table to a regular
expression. You do not have to minimize, but it may help you.
delta | a | b
----+----+---- q1 is the starting state
q1 | q1 | q2 q2 is the final state
q2 | q1 | q2
4) Convert machine given by delta transition table to a regular
expression. You do not have to minimize, but it may help you.
delta | a | b | c
----+------+-----+---- q1 is the starting state
q1 | q1 | phi | q3 q2 and q3 are the final state
q2 | phi | q2 | q3
q3 | q2 | q1 | q3
Closed book. Multiple choice questions based on lectures, reading assignments and homework. Exam covers book: 1.1, 2.1-2.7, 3.1, 3.2, 7.1 Exam covers homework: HW1-HW4
Problems from book page 71,72,74: 3.1 a) 3.1 b) 3.1 c) Extra credit 3.1 d) 3.1 e) 3.1 f) 3.10 sets are equal, or one is a subset of the other 3.25 see Selected Lecture Notes, Lecture 12
For the machine shown below:
1) M = (Q, Sigma, delta, q0, F)
Q = ?
Sigma = ?
delta = ?
q0 = ?
F = ?
2) L(M) = ?
3) give the grammar that has the same language as this machine
G = (V, T, P, S)
V = ?
T = ?
P = ?
S = ?
4) use the longest string in L(M) and show that the grammar accepts it.
(One way to do this is to write the string, then rewrite the string
each time a production applies, with the variable replacing its
pattern. The string is accepted if the result is the start variable)
See Selected Lecture Notes, Lecture 13
Be neat. Show tables as tables. Show sets in { }
Last updated 10/19/98