CS3331 – Assignment 1

CS3331 – Assignment 1

1. (60pt) For each of the following languages, prove whether it is regular or not. If it is, then
- construct a NDFSM for it
- convert the NDFSM into a DFSM (Note that you do not have to include trap/dead states)
- minimize the DFSM
- convert one of the machines into a regular expression (whichever gives a simpler regular expression)
Show your work.
Note 1: If you can give directly a DFSM, then you don’t have to provide a NDFSM. If you provide
directly the minimal DFSM, you still need to argue why it is minimal.
Note 2: Horribly looking regular expressions from JFLAP are acceptable only when no obvious
simpler ones can be found. Usually, JFLAP gives better looking regular expressions from “smaller”
machines, deterministic or not.
(a) {w
RwwR | w ∈ {a, b}
∗}.
(b) {w ∈ {0, 1}
∗
| w has 1010 as substring}.
(c) {w ∈ {0, 1}
∗
| w does not have 1010 as substring}.
(d) {w ∈ {a, b}
∗
| every b in w is immediately preceded and followed by a}.
(e) {w ∈ {a, b, c}
∗
| the third and second from the last characters are b’s}.
(f) {w ∈ {a, b}
∗
| (#a(w) + 2#b(w)) ≡ 0 (mod 4)}. (#a(w) is the number of a’s in w).
(g) {w ∈ {a, b}
∗
| #a(w) − 2#b(w) = 0}.
(h) {w ∈ Σ
∗
| w is a C comments}, where Σ is the keyboard alphabet; C comments are of two
types:
/* ... comment ... */
// ... comment ... \n
2. (20pt) Recall the Multi-Pattern Searching problem is: Given several patterns p1, p2, . . . , pk ∈ Σ
∗
and a text T ∈ Σ
∗
, find all occurrences of pi
’s in T. It can be solved in linear time by constructing
a DFSM for the regular expression Σ∗
(p1 ∪ p2 ∪ · · · ∪ pk) and then run the text T through it; every
time the machine is in an accepting state, we report the end of an occurrence of the patters.
Assume Σ = {i, f, n, t, x} (x stands for any character different from i, f, n, t.) Construct the
minimal DFSM to solve the multi-pattern searching problem for the patterns p1 = if, p2 = int.
(This is used for keyword identification.) Show your work. You are allowed to use Thomson’s
construction or directly build an NDFSM.
3. (20pt) Show that the following problem is decidable:
Given Σ = {a, b} and α a regular expression, is it true that L(α) contains only non-empty
even-length strings in Σ∗ and no string consisting only of b’s?
1
You are allowed to use any of the following:
– closure properties: union, concatenation, Kleene star, complement, intersection, difference
– conversion algorithms between DFSM, NDFSM, regular expressions, and regular grammars (see
the last slide of Ch.7: Conversions)
– decision algorithms: membership, emptiness, finiteness, totality, equivalence, minimality.
Explain which closure property and algorithm you have used. Any other construction or algorithm
should be described in the assignment.
Note: Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be typed but high quality
hand written solutions are acceptable. Make sure you submit everything as a single pdf file.
Note: You are allowed to use JFLAP to solve the assignment. But remember that JFLAP will not be
allowed during the midterm exam!
2