-1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ It has to be a string? $\endgroup$ – Renato Sanhueza Nov 22 '15 at 19:27
  • $\begingroup$ No, but I thought a string would be the most obvious way to give input to a (text-based) program. $\endgroup$ – mavavilj Nov 22 '15 at 19:34
  • $\begingroup$ 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. $\endgroup$ – Anton Trunov Nov 22 '15 at 19:49
  • $\begingroup$ 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). $\endgroup$ – Rick Decker Nov 22 '15 at 19:49
  • 1
    $\begingroup$ Storing data as a parseable string sounds like a programming question to me, not computer science. $\endgroup$ – David Richerby Nov 22 '15 at 20:20
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.