(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 ex-pression)
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.
fwRwwR j w 2 fa; bg g.
fw 2 f0; 1g j w has 1010 as substringg.
fw 2 f0; 1g j w does not have 1010 as substringg.
fw 2 fa; bg j every b in w is immediately preceded and followed by ag.
fw 2 fa; b; cg j the third and second from the last characters are b’sg.
fw 2 fa; bg j (#a(w) + 2#b(w)) 0 (mod 4)g. (#a(w) is the number of a’s in w).
(g) fw 2 fa; bg j #a(w) 2#b(w) = 0g.
fw 2 j w is a C commentsg, where is the keyboard alphabet; C comments are of two types:
/* ... comment ... */ // ... comment ... nn
(20pt) Recall the Multi-Pattern Searching problem is: Given several patterns p1; p2; : : : ; pk 2 and a text T 2 , nd 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 = fi; f; n; t; xg (x stands for any character di erent 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 identi cation.) Show your work. You are allowed to use Thomson’s construction or directly build an NDFSM.
(20pt) Show that the following problem is decidable:
Given = fa; bg 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, di erence
{ conversion algorithms between DFSM, NDFSM, regular expressions, and regular grammars (see the last slide of Ch.7: Conversions)
{ decision algorithms: membership, emptiness, niteness, 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 le 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 le.
Note: You are allowed to use JFLAP to solve the assignment. But remember that JFLAP will not be allowed during the midterm exam!
2
