Questions tagged [transition-systems]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
130 views

How does a Turing machine read a transition table as a function?

I am learning about Turing machines. I understand the alphabet set of symbols and the states a machine can be in. However, I do not understand how the transition function works. I come from a maths ...
Eris's user avatar
  • 13
0 votes
1 answer
303 views

Extended transition function in NFA

The following statement seems trivial, but how can it be formally proven/argued? $$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\...
Ronald's user avatar
  • 89
0 votes
1 answer
101 views

Transition System vs State Machines

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 (...
Jahid Chowdhury Choton's user avatar
2 votes
0 answers
56 views

Definition of nondeterministic transition system in Principles of Model Checking

In Sec 2.1 of Principles of Model Checking, by Christel Baier and Joost-Pieter Katoen, the authors talk about what constitutes a deterministic transition system (T.S.), and mention two kinds - action-...
Motorhead's user avatar
  • 282
1 vote
1 answer
83 views

When is a stuck state not final and when is a maximal sequence not complete in transition systems?

Reading the book Practical Foundations for Programming Language. In section 5.1 Transition Systems, the author said that Whereas all final states are, by convention, stuck, there may be stuck states ...
chansey's user avatar
  • 285
1 vote
0 answers
18 views

Has the similarity relation of a tree-shaped labelled transition system have finite index?

Let $T$ be an infinite countable labelled transition system with the shape of a tree and let $\sim$ be its similarity relation among nodes. Note that the alphabet of the labels is finite (hence the ...
Nicola Gigante's user avatar
0 votes
1 answer
131 views

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase? For example, for the SAT problem, the first question is whether the Boolean ...
lz9866's user avatar
  • 315
-2 votes
2 answers
756 views

Drawing transition diagram from transition table

I have a DFA transition table like \begin{array}{cc|c|c} & & 0 & 1 \\ \hline \to & p & qs & q \\ * & q ...
Manjoy Das's user avatar
1 vote
1 answer
2k views

NFA designing for strings starting with $01$

The question was asked Construct an NFA with set of all strings that start with $10$. The solution provided to me is But my question is what if the automaton receives an input $0$ at the starting? ...
Manjoy Das's user avatar
2 votes
1 answer
54 views

Reducing infinite paths of a transition system to its set of sets of states

Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is ...
Sindri P.'s user avatar
0 votes
1 answer
58 views

Stratification of Bisimilarity : $\sim$ does not coincide with $\sim_\omega$

I am reading Sangiorgi's paper On the origins of bisimulation an coinduction. Definition 2.5, on page 5, defines Stratification of Bisimilarity: Let $W$ be the states of an LTS. We set: $\sim_0 \...
Bromind's user avatar
  • 121
2 votes
0 answers
206 views

Bisimulation, bisimulation equivalence and simulation equivalence?

I got a little confused with these 3 concepts. Is there a difference between bisimulation and bisimulation equivalence and if yes, then what is it? Also, if we say that the LTS's X and Y are bisimilar,...
Sreten Jocić's user avatar
2 votes
1 answer
147 views

Restriction and re-labeling on CCS

In a process like $$ R \stackrel{def}=((a.\bar{b}.0)\setminus\{b\})[a\to b]\mid(\bar{b}.b.0)+\bar{b}.c.0 $$ $b$ is restricted to perform on the inner process of RHS $(a.\bar{b}.0)\setminus\{b\}$, ...
Amir-Mousavi's user avatar
0 votes
1 answer
120 views

State Machine and State transition Table - Explanation and Creation Of

How do I create a state transition table/array in actual code/pseudo-code? I haven't experienced the "ah-ha" moment yet with the state machine to coding (and I really want to). I've looked at several ...
GisMofx's user avatar
  • 123
1 vote
1 answer
142 views

CCS synchronization

Within CSS we talk about binary interactions. Does this prevent synchronizing multiple processes in one step? Example: $P_1 ::= a.D$ $P_2 ::= \overline{a}.D$ $P_3 ::= a.D$ Let's consider the ...
MoreOver's user avatar
  • 135
2 votes
1 answer
656 views

Modeling a sequential circuit as a transition system

I was asked to model the following sequential circuits C1, C2 as transition systems (i.e. identify the output y function and register functions r1, r2, r3) For C2 there appears to be not input x and ...
jn025's user avatar
  • 123
2 votes
0 answers
156 views

Proving weak simulation

I want to prove something but I am not sure if it is the right way to do it. I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is ...
Mr. D's user avatar
  • 121
2 votes
1 answer
978 views

The Interleaved Transition System for 2 Independent and Concurrent Transition Systems

This question is about Model Checking for Software Formal Verification How do you model the joint behavior of 2 independent and concurrent transition systems? Specifically, given the two independent ...
eyeezzi's user avatar
  • 123
7 votes
4 answers
4k views

What is the difference (if any) between transition systems and finite automata?

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)?
Isha's user avatar
  • 73
1 vote
0 answers
94 views

Example of Zeno timed automaton

Is there an example of a timed automaton that requires infinite clock precision, in order to be controller so as to avoid a deadlock or bad state? I.e. a transition system that consists of nodes ...
tmlen's user avatar
  • 111
2 votes
0 answers
45 views

How to prove that justice isn't enough to produce all naturals?

I'm doing the exercises from the first chapter of the book "Temporal Verification of Reactive Systems Safety" by Manna and Pnueli. However I find very difficult to solve the point c of problem 0.2. ...
Bakuriu's user avatar
  • 807
3 votes
2 answers
1k views

Modelling a basic sequential circuit as a transition system?

I'm going through Dr Joost-Pieter Katoen's slides and stumbled upon this: For some reason I can't quite make out how the transition system relates to the sequential circuit. If I had a question for ...
eyes enberg's user avatar
0 votes
1 answer
382 views

Applying DFS algorithm to a transition system to find reachable states

Currently working on a past exam question which tells me to compute the product of two transition systems and then use DFS to find the reachable states of the product. I learnt how to compute the ...
eyes enberg's user avatar
3 votes
1 answer
3k views

What is the difference between a Transition System and a Program Graph? (model checking) [closed]

As the above question says. I'm wondering if a transition system is the same as a program graph or they are two different things? Thank you.
Deyaa's user avatar
  • 33