6
$\begingroup$

is there any difference between transition systems and finite automata? Is it that transition systems consist of both NFA (nondeterministic finite automata) and DFA (deterministic finite automata)?

$\endgroup$
4
$\begingroup$

Yes, did you try wikipedia?

To quote the second paragraph [in transition systems]:

  • The set of states is not necessarily finite, or even countable.
  • The set of transitions is not necessarily finite, or even countable.
  • No "start" state or "final" states are given.
$\endgroup$
2
$\begingroup$

The difference is mainly that automata are a model of machines/programs/.. while transition systems are a model of machine/program/..'s behaviour. So one does not have the same questions and requirements for them.

You are right in thinking that they look the same: some version of directed graphs decorated in some way. However, what is important in mathematics (as in object-oriented programming) is not the objects themselves but the operations they support.

Imagine asking what is the difference between points in $\mathbb{R}^3$ and vectors in $\mathbb{R}^3$? They both are triples of numbers, no? Well, yes but this is not the point. Vectors are displacements so it is meaningful to add them, scale them. Points cannot be added meaningfully. They can be subtracted, as in $B - A$. BTW, this gives you a vector, hence $B-A$ is usually denoted $\vec{AB}$.

$\endgroup$
2
$\begingroup$

What you probably mean by transition system is a Kripke structure Basically you can call any directed graph with labeled vertices a transition system.
But finite automaton is a concept and includes any language deciding machine with finite memory. DFA and NFA are specified kinds of finite automaton and they can decide all the languages decidable by any other kind of finite automaton.
DFA and NFA are like transition systems with additional constraints:
In both cases:
- Edges should be labeled by the members of the alphabet
- A start state should be specified
- A set of final states should be picked
In DFA only
- Each state should have exactly one outward transition for every member of the alphabet

$\endgroup$
0
$\begingroup$

Another note, in transition systems the state is often a set of variables (atomic propositions, boolean vectors, etc.). Whereas in automata the state is almost always a label (a simple identifier such as a name or an integer or an id type of thing). The state doesn't contain anything in automata, whereas it does in transition systems.

$\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.