1
$\begingroup$

I haven't found a good enough answer by googling. Here's what i know:

  1. TG's can have more than one initial state
  2. In TG's, Edges/transitions can be labelled with strings
  3. In TG's, it is not necessary to show transitions for all letters

Notes:

  • I am talking about plain TG's, not GTG's and DFA's only not NFA
  • Only thing i know about NFA's is that each a state can have multiple transitions for the same letter, so please keep that in mind if hte answer invloves NFA's
  • Links would be appreciated.
$\endgroup$
  • $\begingroup$ I’ve never heard of transition graphs. $\endgroup$ – Yuval Filmus Dec 2 '18 at 18:17
  • $\begingroup$ @YuvalFilmus , exactly, i can't find something definitive either. the internet seems to think TG is what i think FA is. so i am not sure how they are different, i am on a distant learning platform and low quality material, so they use these words interchangeably, only difference their notes (that's right, no textbooks) tell are listed above. they also always use FA where they mean a DFA. Take a look here and here $\endgroup$ – Awaisome Dec 3 '18 at 3:26
  • $\begingroup$ @YuvalFilmus would it be right to say that FA is a theoretical machine and it's diagram is what we call a TG. but then why did my notes specify differences between the two as i listed above. I think it's because in my notes DFA is referred to as FA. so a TG is the diagram of both a DFA and NFA, but since they referred to DFA as only FA and we haven't read about NFA yet, that's why they had to specify the differences, because in the notes FA only means DFA and not NFA. clear as mud, right? $\endgroup$ – Awaisome Dec 3 '18 at 3:38
  • $\begingroup$ @YuvalFilmus this site has the same notes my university provided me in pdf with better looking diagrams, i don't who copied whose. here's lecture 4 in my notes where they tell what an FA is (there's no index, CTRL+F for finite automaton) and here's lecture 7 where they talk about TGs. $\endgroup$ – Awaisome Dec 3 '18 at 3:42
  • $\begingroup$ Do they mean transition systems? $\endgroup$ – reinierpost May 2 '19 at 6:59
1
$\begingroup$

Your nomenclature is highly nonstandard. It seems that "finite automata" are what are usually known as DFAs, whereas "transition graphs" are a special case of GNFAs in which the only regular expressions allowed are words; alternatively, they are like $\epsilon$-NFAs, only transitions can be marked by arbitrary words (rather than just words of length at most 1).

There are two differences between your FAs and your TGs:

  1. FAs are deterministic: at each point in time, there is exactly one choice of which state to go to next. There is no such restriction on TGs. Moreover, whereas FAs have a unique initial state, TGs have an arbitrary number of initial states.

  2. Transitions in FAs are labeled by symbols. In contrast, transitions in TGs are labeled by words.

These are exactly the differences that you listed.

$\endgroup$
  • $\begingroup$ the notes my uni provided don't mention GNFAs but GTG or generalized TGs whose only difference from TGs is that the edges are labelled with regex. I am just starting the course so i hope it will be clear by the time.i finish the basics. i have asked a more practical question, no replies yet. kindly take a look $\endgroup$ – Awaisome Dec 3 '18 at 5:49
  • $\begingroup$ I contacted the faculty, their reply: "In an FA, there must be a single out going edge for each input character at each state. Loop is considered as an outgoing edge. TG is more flexible than FA. The edges may be omitted in TG, substrings can be mentioned on edges as well as the NULL character. In non-deterministic FA (NFA), the outgoing edges may be missing for some alphabets or there may be present more than one edge for the same alphabet." This was all already in the notes. Doesn't help. I have downloaded proper notes. $\endgroup$ – Awaisome Dec 3 '18 at 5:53

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.