3
$\begingroup$

I've recently come across a few articles that talk about a "Generalized Transition Graph" (GTG), but I've never heard of such a thing before. This other answer to a similar question leads me to believe that GNFAs are simply GTGs with a different name where GNFA is the more standard nomenclature/name.

There is a Wikipedia article on GNFAs that describes them as:

...a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression.

which from what I understand is described by others as a GTG. Unfortunately, there's no article on Generalized Transition Graphs on Wikipedia. The definitions for GTGs that I have come across are:

So again, are GNFAs the same as GTGs?

$\endgroup$
3
  • $\begingroup$ Can you compare the two definitions? $\endgroup$ – Yuval Filmus Apr 1 at 16:12
  • $\begingroup$ The first link at least states: "Every finite automaton can be viewed as a transition graph.•Since the reverse is not true, transition graphs generalize finite automata." But what remains unclear whether GTG recognizes exactly the same languages as FAs... $\endgroup$ – Roman Susi Apr 2 at 11:16
  • 1
    $\begingroup$ Transition graphs seem to be slightly more general. In the wikipedia definition GNFA's are required to have only a single initial/start state (without incoming edges) and only a single final/accept state (without outgoing edges). The GTG I found in one of the slides may have multiple such states. For the language descriptive power this is of no consequence. Both models allow regular expressions as label of the edges, thus both of these define the regular languages. $\endgroup$ – Hendrik Jan Apr 2 at 22:04

Your Answer

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

Browse other questions tagged or ask your own question.