Homework 1 Solution

Question 1 | Question 2

Question 1

Part a

L(M) = {a, aa, aaa}

Part b

State s eclose(s)

p0 {p0, p1, p2}

p1 {p1, p2}

p2 {p2}

p3 {p3, p4}

p4 {p4}

State s	eclose(s)
p0	{p0, p1, p2}
p1	{p1, p2}
p2	{p2}
p3	{p3, p4}
p4	{p4}

Part c

Equivalent NFA with no epsilon transitions

Part d

Note: the labels on the DFA states indicate the corresponding NFA states from Part c that are in the set for that DFA state, e.g., state p3p4 corresponds to {p3, p4}.

Question 2

Part a

{SLASH}{STAR}[^(*/)]*{STAR}{SLASH}

Doesn't allow parentheses, stars, or slashes in the comment body: /* (*)(/) */

{SLASH}{STAR}(.)*{STAR}{SLASH}

Allows */ in the comment body: /* a */ */
Doesn't allow a newline in the comment body:
/* this is a multi-line comment */

{SLASH}{STAR}([^*]*{STAR}+[^*/])*{STAR}+{SLASH}

Doesn't allow a non-empty comment body without a star: /* a */

{SLASH}{STAR}([^*]|[^/])+{STAR}{SLASH}

Allows */ in the comment body: /* */ */
Doesn't allow a comment with an empty body: /**/

{SLASH}{STAR}[^*]*{STAR}+{SLASH}+

Allows multiple / after the end of the comment: /* *////
Doesn't allow non-star to appear after a star in the comment body: /* *a */

Part b

{SLASH}{STAR}([^*]|({STAR}+[^*/]))*{STAR}+{SLASH}