This assignment involves the construction of a NFA-to-DFA program. You are to work by yourself.

Given a NFA, M₁ = (Q_n, _n , _n, s_n, F_n), write a program that will convert it to a DFA, M₂ = (Q_d, _d,

_d, s_d, F_d). The states in Q_n are zero-indexed integer values. This means 0 is a state, if |Q_n| = 3, then Q_n= {0, 1, 2}. The alphabet, _n = _d = , is restricted to lowercase letters.

The format for the input will consist of the following components, each on separate lines:

|Q_n| The cardinality of Q_n

In the form of a non-delimited string

|F_n| F₁ F₂ ... F_k The cardinality of Fn, followed by each of the accepting states, separated by

whitespace where k = |F_n|

s_n The start state

Finally, _n, the transition function, each on a line, given in 3-tuples, q_i a q_j. q_i and q_j are integer values, and a is a symbol in the alphabet, , with a space separating each.

The input example that follows is similar to Fig. 2.9 from the text on page 56:

3 ab

1 2

0

0 a 0

0 b 0

0 a 1

1 b 2

The format of the output mirrors the input. It will consist of the following components, each on separate lines:

|Q_d| The cardinality of Q_d

In the form of a non-delimited string

|F_d| F₁ F₂ ... F_k The cardinality of Fd, followed by each of the accepting states, separated by

whitespace where k = |F_d|

s_d The start state

Finally, _d, the transition function, each on a line, given in 3-tuples, q_i a q_j. q_i and q_j are integer values, and a is a symbol in the alphabet, , with a space separating each.

Output produced from example:

3 ab

1 2

0

0 a 1

0 b 0

1 a 1

1 b 2

2 a 1

2 b 0