# Questions tagged [finite-state-machine]

For questions about finite state machine, which is a mathematical model of computation.

73 questions
Filter by
Sorted by
Tagged with
9 views

### What would be the output for this state table?

I am having doubts on how to do the karnaugh map for the output of this state table: Since the output has 2 variables how can I make a karnaugh map with the output result? For example for the state ...
22 views

### Average Cost Incurred by Probabilistic Automata

Let's say I have a probabilistic automata, but in addition to weights for each transition, there is also a cost associated with each transition. For example, consider this simple state machine: q1 can ...
1 vote
31 views

### Can NFAs have infinitely many edges?

This question is about whether the definition of weighted Non-deterministic Finite state Automata (NFAs) excludes the possibility of infinitely many transitions. The definition of Finite State ...
38 views

### Proof of Pumping Lemma: Why can we set the pumping constant to the number of states?

I'm learning the proof of the Pumping Lemma for regular languages. The proof is carried out using an arbitrary string having length of at least the number of states in the DFA. As such: The language ...
• 1
57 views

### FSM and regular language

Here is a finite state machine which can be recognised with a regular language. The regular expression which I've got for this FSM is: (10(0+(10))*11+11+00*10(0+(10))*11+00*11)(0+1)* Is this correct? ...
• 33
132 views

### How to design a Mealy machine which is divisible by 3 or by 2.

How do I design a Mealy machine which outputs 1 if the binary number is divisible by 3 or by 2 considering the LSB is coming first? Appreciate the help!
• 39
52 views

### Understanding languages for Finite State Automata

Hi I'm learning about finite state automata. I understand what a language is but I don't understand what this syntax is telling me about it. $L = {\{a,b\}}^{*}{\{aa,bb\}}{\{a,b\}}^{*}$ Could you help ...
15 views

### is N-Σ-automaton a Non-Deterministic Finite Automata

I am trying to understand a part of this book Automata,Languages and Machines. K=N case I cant undesrtand the Topic because i dont get what a N-Σ-automaton, i tried to find something, but i only get ...
1 vote
29 views

### Guaranteed recurrence in any finite system?

Sorry if this is in the wrong forum. This video puts forward the popular belief that given enough time, a finite system can only exist in finitely many states, and so it must return to its starting ...
• 605
1 vote
44 views

### What is the most unambiguous digraph representation of NAND/NOR?

Is there an official or standardized way to represent the basic boolean operations with directed graphs? (I don't mean like in circuit diagrams.) If so, what is it? And if not, I would also accept an ...
• 5,211
1 vote
17 views

### On the notation of the hierarchy function of a state (statecharts)

I'm reading the prof. Harel's On the formal semantics of Statecharts. I know it might be quite difficult to answer this question without a context so I hope someone's familiar with Dr. Harel's work. ...
• 1,248
1 vote
11 views

### Choosing best observations for certain goal

I have a set of $n$ observations $O_j = (a_j, b_j)$ I have a state $S_j = (A_j, P_j)$ with an initial state $S_0 = (0,0)$ I must consume all my observations, such that my final state has its $P_j$ at ...
• 171
28 views

### What is Cover(M) of a marking M in a Timed Petri Net (TPN)?

The background paper for my questions can be found here (in particularly, pages 3 and 4) - I highly recommend reading chapter 2 (found in pages 3 and 4) to be able to reason with the definitions ...
• 13
1 vote
171 views

### Will this finite state machine reject this number?

I constructed the following acceptor $M_1$: Formal Definition: $M_1=(Q,Σ,δ,q_1,F)$ $Q = \{q_1,q_2,q_3\}$ $Σ = \{0,1\}$ $δ =$ (see diagram) $F = \{q_3\}$ $M_1$ processes a word $w = w_n…,w_3,w_2,w_1$ ...
15 views

### Do I need mealy, moore, or something else to model this state diagram?

Let's say I have these states: started, paused, stopped,uninitialized, and error. And these inputs: init, start, pause, stop, dispose. And the machine,a blackbox, let's call it M. The machine also has ...
• 143
270 views

### Random search for very big Collatz conjecture counter-examples

I know that exhaustive search was done to test numbers up to 2^68. This seems like a big number but when looking at Collatz function as a Turing machine manipulating some input bit sequence, only ...
• 159
138 views

### Prove\Disprove: If $L_1$ is not a CFL, and $L_2$ is finite, then $L_1 \cup L_2$ is not a CFL.

I am getting ready for finals, and encountered this question in a past assignment. I haven't proved this then and I don't understand how I can prove it now. Prove\Disprove: If $L_1$ is not a Context-...
• 1
114 views

### Finite State Machines: Can a state diagram have more than one self-loop?

According to Schaum's Outlines, the state diagrams of Finite State Machines are labelled directed graphs. Now, it is entirely possible that the resultant state after transition returns to itself more ...
1 vote
79 views

### If L is regular, then $L \setminus \{ \epsilon \}$ is regular.

I need to show that if $L$ is regular language, then $L \setminus \{ \epsilon \}$. I was thinking: If $L$ contains $\epsilon$, then in the FSA the start state is a final state. But by making the start ...
• 479
1 vote
59 views

### Is Shuffling of a regular language regular too?

If $A$ be regular language, How we can prove that $A^{'}$ is regular too? $A^{'} = \{a_{2}a_{1}a_{4}a_{3} ... a_{2n}a_{2n-1} \mid a_{1}a_{2}a_{3}...a_{2n} \in A\}$ Is there any way to prove that even/...
• 133
27 views

### Pumping Lemma to prove language not regular, formatting $x$

I need help with a question/verification I'm even thinking about it correctly. I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This ...
80 views

• 317
1 vote
67 views

### Calculating a transition probability in FSM

I have a Finite State Machine represented in following form: ...
• 113
91 views

### Finite State Automata

it's been a while since I've done FSA's so I'm a little rusty, bear with me. I'm creating an FSA to parse Integer and Decimal tokens for a class. The two tokens have the regex Integer: $0|[1-9][0-9]^*$...
• 383
1 vote
65 views

### Non-linear recurrence relation with Kronecker delta

I am studying a game in number theory and I have come across some non-linear (coupled) recurrence relations which involve what I've been referring to as Kronecker deltas (or unit sample functions). An ...
13 views

### Are the following conversions from DFAs to GNFAs correct?

This machine (a) should accept all strings that start with a 1 and end with a 0. This machine (b) should accept all strings that contain three or more 1s. This machine (c) should accept all strings ...
• 405
125 views

### Floyd Invariant Principle on a deck of cards [closed]

The below problem has been taken from Mathematics for Computer Science (MIT Opencourseware https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-...
• 722
1 vote
153 views

• 117
1 vote
435 views

### Epsilon Non Deterministic Finite Automata proof

Let M = (Q, Σ, δ, q0, A) be an ε-NFA and let S ⊆ Q. Prove that ε(S) = ε(ε(S)). I will provide some definitions that may be useful in answering the question Formal Definition of ε-NFA M = (Q, Σ, δ, ...
• 25
1k views

### Regular Language accepted by a Finite State Machine

If L is a finite-size language then L is a regular language, meaning that it can be accepted by a finite state machine. Prove this by defining how to build—for any finite-size language L—a finite ...
• 25
280 views

### Deterministic Finite State machine for a Language

Suppose L is a regular language, and M = (Q, Σ, δ, q0, A) is a deterministic finite state machine such that L(M) = L. Prove that if |Q| = 2 then one of the following hold: (i) L = ∅ (ii) ε ∈ L, or (...
• 25
1k views

### What is the period of Langton's ant on a torus?

Langton's ant runs on an infinite white grid. At every white square, it turns right, flips the color of the square, and moves forward one square. At every black square, it turns left, flips the color ...
• 370
1 vote