For this problem, let Σ = {a, b}.
- Draw a DFA M1 for which
L(M1) = {x ∈ Σ* | x begins with b}.
- Draw a DFA M2 for which
L(M2) = {x ∈ Σ* | #b(x) is even}.
- Use the Product Construction described on page 22 of Kozen to build
a DFA M3 for which
L(M3) = L(M1) ∩ L(M2).
- Is it possible to construct a DFA for L(M3)
using fewer states than M3 has? If so, show such
a DFA. If not, give a brief explanation (not a formal proof) why not.
Consider the DFA M described by:
Q = {0, 1}
Σ = {a, b}
s = 0
F = {1}
and
- Describe L(M) in English.
- Prove your answer correct.
In which the intrepid students investigate the regularity of finite sets...
- If I give you a finite set of strings over an alphabet
Σ, is it possible to create a DFA M
for which L(M) is equal to that finite set?
(Hint: yes.) Briefly describe a procedure for doing so.
- Illustrate your procedure by drawing a DFA named M
over the alphabet {a, b} for which
L(M) = {aba, abb, abba, baa, baba}.
(This set, by the way, is the complete set of English words of three
or more letters consisting entirely of a's and b's, according to
SOWPODS.)
For each of the following, provide Python code using the
re module to accomplish
the specified task. (Once you have something that seems to be working,
think again about ways in which a string could fool your regular expression.)
- Extract the first word in the string s
that both begins and ends with a lower-case letter.
- Print the starting and ending indices of all the words in the
string s that both begin and end with a
lower-case letter. For example, if s = "The moose is disgruntled.",
you should print something like:
4 9
10 12
13 24
Note that the ending index is the index of the character immediately
following the word.
- Replace all occurrences in the string s
of the words "Doctor" or "Dr." into
"The Good Doctor" or "The Good Dr.", respectively, except when
"Doctor" or "Dr." is followed by " Evil". That is, "I enjoy
conversations with Dr. Schweitzer" would become "I enjoy
conversations with The Good Dr. Schweitzer", but "Doctor Evil
is not very nice" would remain unchanged.
- Try to transform the string s into
Ubbi dubbi.
Once you have a rough version of an Ubbi dubbi translator, describe
the errors your version will make. Are regular expressions capable
of fixing those errors?