Thompson construction to output an NFA

[imraniac]

Implement:

• [x] Basis / Two cases (epsilon, single symbol)
• [x] Induction / Three operations (closure, union, concat)

---

• [x] Depends on #1
• [x] Depends on #6 partially (NFA)

[287mdsahil]

Please discuss the data structures used to represent an NFA.

[imraniac]

NFA structure will have

1. Two maps for epsilon and symbol transition, from one state to another.
2. An array list: collection of all the NFA states

The NFA state struct will have "isFinal" attribute. Is anything else needs to be added? @pmcarpan

[pmcarpan]

• You can make a transition class if you want with the type attribute denoting epsilon/non-epsilon transitions.
• A Set for the final states may improve lookup time?
• Have some static methods to get NFAs for the base cases of the Thompson algorithm.

Suggestion: make the Thompson algo a separate class with only static methods?

What do you mean by "isFinal" attr in state struct?