0
$\begingroup$

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (for describing its language). I just want to know about the basics. Can I call a DFA a transition system (because DFA is a state machine, but never saw it be called a transition system)? NFA/DFA are finite state machines (FSM) and transition systems can have a finite or infinite set of states (does it mean it is an infinite state machine?). A more basic question, is every "state machine" a "system" or vice versa? What is the difference between "machine" and "system"? Why we are not calling "Transition Machine"?)

(Note: I asked the same question in Mathematics Stack Exchange but got no answer. That is why posting it in here.)

Improve this question
$\endgroup$
6
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/4503612/14578, cs.stackexchange.com/q/153366/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2022 at 20:01
  • $\begingroup$ Hello. I did not received any answer that is why I posted here. Should I delete the previous post in the other site? $\endgroup$
    – Jahid Chowdhury Choton
    Commented Aug 1, 2022 at 20:02
  • $\begingroup$ I encourage you to pick one site where you want your post to appear. If you realize you have posted on the wrong site, I recommend that you delete your question on the original site before posting it elsewhere (and make sure to update it based on any comments/feedback you receive). $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2022 at 20:06
  • $\begingroup$ There is another stack exchange site only for CS theory (I didn't know that). Should I delete in both sites and post in there? $\endgroup$
    – Jahid Chowdhury Choton
    Commented Aug 1, 2022 at 20:09
  • 1
    $\begingroup$ No. Once you've received an answer somewhere, it is considered impolite to delete your question and ask somewhere else. And this is not a research-level question, so it is not suitable there. It is important to read the help center on sites you are considering posting to, to understand their requirements (cstheory.stackexchange.com/help/on-topic). $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2022 at 20:19

1 Answer 1

Reset to default
1
$\begingroup$

From each DFA or NFA, you can obtain a labelled transition system, by ignoring which states are the initial or final states.

If you have a labelled transition system with a finite set of states and a finite alphabet, as well as an initial state and a set of final states, you can define a corresponding NFA.

See https://en.wikipedia.org/wiki/Transition_system, which has answers to several of your questions. In general, I recommend reading standard resources (such as textbooks and Wikipedia) before asking here, to ensure that your question is not already answered in them.

The difference between "machine" vs "system" is just an arbitrary choice and has no particular meaning in this context.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You said ignoring the initial or final states, but transition system and DFA both has initial states. A transition system is a Tuple (S, Act, ->, s0, L) which is defined in one of the model checking book I am reading (s0 is the initial state). (Book name: Principles of Model Checking by Christel Baier) But there are no final states. But in Wikipedia there are no initial states in transition systems. I'm a little bit out due to several different definitions. As you said I can make a DFA from labelled TS, but can I make the opposite? (Finite Machine to Transition System?) $\endgroup$
    – Jahid Chowdhury Choton
    Commented Aug 1, 2022 at 20:20
  • $\begingroup$ @JahidChowdhuryChoton, that might depend on the specific definition used. Please adjust accordingly. Regarding your last question, see the first sentence of my answer. $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2022 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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