# Programming Thompson's algorithm: How to represent a NFA?

I'm trying to create a small program that interprets a NFA to the corresponding regex using Thompson's algorithm.

My question: What kind of notation can be used to express a NFA (e.g. in the form of a string?) that can be read and then interpreted by the program?

• It has to be a string? – Renato Sanhueza Nov 22 '15 at 19:27
• No, but I thought a string would be the most obvious way to give input to a (text-based) program. – mavavilj Nov 22 '15 at 19:34
• How about this ->(q0) q1 (q2) # q0 0 q2, q0 1 q1, q0 1 q2 ? "->" means initial state, (q0) - means accepting state, # marks the states and the transition function sections. q0 0 q2 means $\delta(q_0, 0) = q_2$. The parser should infer the alphabet. – Anton Trunov Nov 22 '15 at 19:49
• At the very least, you'll have to provide a description of the transitions in your NFA. Since a NFA might have a transition like $\delta(q_A, x)=\{q_A, q_C, q_D\}$, you'll need pieces like $(A, x, A, C, D)$ to indicate that transition. There's some necessary complexity here, but it can be done (as I know from experience). – Rick Decker Nov 22 '15 at 19:49
• Storing data as a parseable string sounds like a programming question to me, not computer science. – David Richerby Nov 22 '15 at 20:20

If you look closely, Thompson's R.E. to NFA algorithm is carefully tuned to be able to use a simple linked structure: a state is a node, it has one leaving transition on a symbol, or two on $\epsilon$ (thus you can reuse the space for the symbol for the second pointer, and distinguish between both cases by a spare bit somewhere). Your partial automata have one start and one accept state, so you need two pointers for each one, and splicing them together is again simple link manipulation.