Due Friday, September 16
1. DFAs (9 points)
Draw Deterministic Finite Automata to accept the following sets of strings over the alphabet {0,1}:
a. All strings that contain
exactly 4 "0"s.
b. All strings ending in
"1101".
c. All strings containing
exactly 4 "0"s and at least 2 "1"s.
d. All strings whose binary
interpretation is divisible by 5.
e. All strings that contain
the substring 0101.
f. All strings that
start with 0 and have odd length or start with 1 and have even
length.
g. All strings that don’t
contain the substring 110.
h. All strings of length at
most five.
i. All strings where
every odd position is a 1.
2. NFAs (6 points)
Draw Non-deterministic Finite Automata with the specified number of states to accept the following sets:
a. All strings containing
exactly 4 "0"s or an even number of "1"s. (8 states)
b. All strings such that the
third symbol from the right end is a "0". (4 states)
c. All strings such that some
two zeros are separated by a string whose length is 4i for some i
>= 0. (6 states)
d. All strings that contain
the substring 0101. (5 states)
e. All strings that contain
an even number of zeros or exactly two ones. (6 states)
f. The language 0*1*0*0. (3
states)
3. Converting NFAs to DFAs (4
points)
a. Convert the NFA in
2f into a Deterministic Automaton.
b. Convert the NFAs on
pages 31-32 in text: 8, 12.
4. Discrete Math Review – Proofs (2 points)
Analyze the two languages below. They are two descriptions of the same language – strings of balanced parentheses.
Language 1: The set of strings where
each string w has an equal number of zeros and ones; and any
prefix of w has at least as many zeros as
ones.
Language 2: The set of strings defined
inductively as follows: if w is in the set then 0w1 is also in the
set; if u and v are in the set then so is uv; and
the empty string is in the set.
a. Prove that every
string in Language 2 is contained in Language 1. (Hint: a
proof by induction is easiest, because Language 2 is defined
inductively).
b. Extra Credit: Prove they are
equal (i.e., Language 1 is also contained in Language 2).
5. Closure Problems (5 points)
You may use examples to illustrate your
proofs. Note a proper prefix is any prefix that is not the empty
string or the whole string itself. Also, note that regular sets
are not closed under subset.
That is, subsets of regular sets are not
necessarily regular. Indeed, a subset is often more
difficult to recognize than the original.
a. Prove that if L1 is
regular and L2 is regular then so is L1-L2 (the set of all strings
in L1 but not in L2).
b. Prove that if L is regular
then Prefix(L) is regular. Prefix(L) is the set of all strings
which are a proper prefix of a string in L.
c. Prove that Regular Sets
are closed under MIN. MIN(R), where R is a regular set, is the set
of all strings w in R where every proper prefix of
w is not in R.
(Note that this is not simply the complement of Prefix).
d. Prove that Regular Sets
are NOT closed under infinite union. (Hint: 0n1n
is not regular.).
e. What about infinite
intersection? Hint: Use DeMorgan's Law
f. Extra Credit:
Prove
that if L is regular so is Half(L). Half(L) is the set of all
first halves of strings in L.
6. Regular Expressions (5 points)
Write regular expressions for each of
the following languages over the alphabet {0,1}. Provide
justification that your regular expression is correct. Note
that converting from a correct finite state machine is one way to
provide valid justification.
a. The set of all strings in
which every pair of adjacent zeros appears before any pair of
adjacent ones.
b. The set of all strings not
containing 101 as a substring.
c. The set of all strings
with at most one pair of consecutive zeros and at most one pair of
consecutive ones.
7. Converting Finite Automata to Regular
Expressions (1 point)
Page 28. Convert
Example 3.9 to a regular expression. Show your work.
8. Regular Expression Identities (3 points)
Prove (give at least a few words of
justification), or disprove (by counterexample) that each pair of
regular expressions represent the same
language. Assume that r, s and t
represent regular expressions over the alphabet {0,1}.
a. r(s + t) and rs + rt
b. (r*)*and r*
c. (r + s)* and r*s*
9. Final States (2 points)
a. Explain why every NFA can
be converted to an equivalent one that has a single final state.
b. Give a counterexample to
show that this is not true for DFA’s.
c. Extra Credit:
Describe
the languages that are generated from a DFA with just one final
state.
10. Miscellaneous Problems (3 points)
a. Draw the minimum
deterministic finite state machine to accept the following regular
expression and succinctly describe the set in English.
[00 + 11 + (01 +
10)(00 + 11)*(01 + 10)]* (Hint: The minimum size
of the machine is 4 states).
b. Show that the following
is a regular language: The strings that
contain an equal number of occurrences of the substrings 01 and
10.