[SOLVED] C algorithm CS3331 Assignment 1

CS3331 Assignment 1
due Oct. 8, 2019 (latest to submit: Oct. 11)
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 ex- pression)
Show your work.
Note 1: If you can give directly a DFSM, then you dont 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) {wRwwR | 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 bs}.
(f) {w {a, b} | (#a(w) + 2#b(w)) 0 (mod 4)}. (#a(w) is the number of as 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

2. (20pt) Recall the Multi-Pattern Searching problem is: Given several patterns p1 , p2 , . . . , pk and a text T , find all occurrences of pis 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 Thomsons 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 bs?
1

Note: Note:
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.
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.
You are allowed to use JFLAP to solve the assignment. But remember that JFLAP will not be allowed during the midterm exam!
2