Homework 2

Problem 1: Convert these REs into NFA’s using Thompson’s construction. Avoid taking “shortcuts”.

(a) for | [a-z]+ | [xb]?[0-9]+
(b) a ( bc*d | ed ) d+
(c) ( a*b | b*a | ba ) *

Problem 2: Convert the NFAs in the previous problem into DFAs using the subset construction method.

(a) from above
(b) from above
(c) from above

Problem 3: Consider how Thompson’s construction would be implemented in code instead of a sketch.

Suppose that each NFA is represented by an object A with the following properties: A[s,i] is the transition matrix yielding the next integer state(s) given current state s and input i; A.start is the integer start state of the NFA; A.accept is the integer accepting state of the NFA; A.states is the number of states in the NFA.

(a) Write out the transition matrix A representing the NFA generated by (a|bc), and give the values for A.start, A.accept, and A.states.
(b) Write out the transition matrix B representing A*, along with B.start, B.accept, B.states.
(c) Write some Python-like pseudocode describing how to apply the Kleene closure to any arbitrary NFA X.