Questions tagged [finite-state-machine]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
3 votes
1 answer
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? ...
user avatar
  • 33
0 votes
0 answers
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!
user avatar
  • 39
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 605
1 vote
1 answer
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 ...
user avatar
  • 5,211
1 vote
0 answers
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. ...
user avatar
  • 1,248
1 vote
0 answers
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 ...
user avatar
  • 171
0 votes
0 answers
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 ...
user avatar
  • 13
1 vote
2 answers
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$ ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 143
4 votes
0 answers
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 ...
user avatar
  • 159
0 votes
0 answers
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-...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
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/...
user avatar
  • 133
0 votes
1 answer
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 ...
user avatar
4 votes
1 answer
80 views

Can we construct groups of several discrete "loops"?

I know that we have cyclic groups. Maybe the groups which in the most easy-to-access way can explain the concept of a generator. But do there also exist groups of two or more loops? For example $\...
user avatar
  • 24.3k
1 vote
1 answer
30 views

Non-deterministic finite automaton-transition function

When we define: $δ:(Q \timesΣ\to2^Q)$ $2^Q$ represents the numbers of transitions or the resulting position after the automaton get letter?
user avatar
  • 157
0 votes
2 answers
93 views

Finding the probability of a multi-state transition in a finite state machine

Finite State Machine Example (cannot embed yet) I'm struggling to understand how to compute the probability of $q_{0} \rightarrow q_{3}$. From my understanding, given that the transition from $q_{1}$ ...
user avatar
  • 13
2 votes
1 answer
126 views

Counting the number of possible strings given some constraints

So this is more of a statement of an interesting approach I found (of solving a particular type of problem) than a question, but I would like to read up more on the subject, if there even is a subject ...
user avatar
  • 123
1 vote
1 answer
80 views

Is Language of All Binary-Digit Strings Not Containing Substring 0100 or Suffix 010 Context-Free?

Let $\Sigma$ be the alphabet consisting of the symbols {0,1}, let $\Sigma^{*}$ be its Kleene closure, and let $R$ be defined by $R = \{w \in \Sigma^{*} \mid (0100 \text{ is not a substring of }w) \...
user avatar
1 vote
1 answer
67 views

Calculating a transition probability in FSM

I have a Finite State Machine represented in following form: ...
user avatar
  • 113
3 votes
0 answers
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]^*$...
user avatar
  • 383
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 405
0 votes
1 answer
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-...
user avatar
1 vote
0 answers
153 views

Generating a finite state machine from regular grammar

Just want to make sure that the way I solved this question is correct since I looked around online and am still not sure about this part: Question: draw a finite state machine that generates $\{0^∗(10+...
user avatar
  • 113
2 votes
2 answers
68 views

Probability from an Unknown State in a Finite State Machine

I'm attempting to model probability for a finite state machine. The probability of the next state depends on the current state. However, I'd like to handle the case where I don't know the starting ...
user avatar
  • 21
1 vote
1 answer
69 views

NFA to DFA Diagram Conversion

I've been tasked with converting an NFA to a DFA in diagram form. The NFA is like so: NFA And my DFA:Updated DFA I have the nagging feeling that I'm missing something in the conversion regarding {1,...
user avatar
0 votes
1 answer
39 views

Using transition matrices for strings with specifcations on string block length

In class we've learned about using transition diagrams to help come up with transition matrices that are composed of either zeroes or ones and which document number of ways to get from state j to i; ...
user avatar
0 votes
2 answers
158 views

Converting NFAs to DFAs

I wanted to find the diagram for the DFA that recognizes $$L=\{w \mid w \text{ starts with }1 \text{ and ends with }0\}$$ Clearly, it is easier to find a NFA first. But I couldn't convert it to a DFA ...
user avatar
0 votes
2 answers
63 views

Deterministic finite machine recognizing language $((00)^*|1(11)^*)^*$

Is the following deterministic finite machine correct for recognizing the language $((00)^*|1(11)^*)^*$? Let $M=(Q,\Sigma,\delta,q_0,F)$ where $Q = \{q_0,q_1,q_2,q_3,q_4,q_5,q_\Delta\}$ is the set of ...
user avatar
  • 290
-1 votes
1 answer
86 views

Construct a deterministic finite machine for the language $(01)^*$

I need to construct a deterministic finite machine that recognizes the language $(01)^*$. This is the machine I have constructed, is it valid? Let $M=(Q,\Sigma,\delta,q_0,F)$ where $Q = \{q_0,q_1\}$ ...
user avatar
  • 290
1 vote
1 answer
51 views

partial recursive functions

Since the partial recursive functions are those that can be computed by a Turing machine, it seems that there ought to be a simple set of restrictions that can be placed on them to get the subset of ...
user avatar
  • 11
3 votes
1 answer
3k views

Equivalence of NFA with and without $\epsilon$-transitions.

I am reading through the first edition of $\textit{Introduction to Automata Theory, Languages, and Computation}$ by Hopcroft and Ullman. They introduce the notions of NFA's and $\epsilon$-NFA's as ...
user avatar
  • 929
1 vote
0 answers
57 views

Can a regular language be defined using recursive regular expressions?

My problem is essentially that I can't find anything that explicitly prohibits or allows such definitions. To illustrate with an example: Our teacher challenged us to create a definition for a ...
user avatar
0 votes
1 answer
193 views

How do I prove that this language is regular?

I'm working on a problem that defines a language $D_n$, here is how $D_n$ is defined: "Consider the language $D_n$ of binary strings representing numbers divisible by some fixed n." The problem is to ...
user avatar
1 vote
1 answer
53 views

Is it possible to design a DFA for these languages?

$$\mathcal{L}_1 = \{1^{\cdot n}w\mid,n\geq1, w \text{ has }n\text{ or more 1's}\}$$ $$\mathcal{L}_2 = \{1^{\cdot n}w\mid,n\geq1,w \text{ has }n\text{ or fewer 1's}\}$$ I am thinking that there ...
user avatar
1 vote
1 answer
1k views

I am trying to find a regular expression for {Strings whose number of 0s is not divisible by 4}, with and without the use of complement.

With use of a complement I found: $$\{ \text{Strings whose number of 0s is divisible by 4\}}^{C} = $$ $$\{\{\{1\}^*\cdot \{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{1\}^*\cdot\{0\}\cdot\{...
user avatar
1 vote
0 answers
38 views

How can I show regular language is closed under square root? [duplicate]

I came across this question when reading a textbook of automata and languages: For $L\subseteq\Sigma^*$, define $\sqrt{L}=\{x\ |\ \text{there exists $y \in \Sigma^*$ such that $|y|=|x|^2$ and $xy\in ...
user avatar
1 vote
1 answer
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, Σ, δ, ...
user avatar
  • 25
0 votes
1 answer
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 ...
user avatar
  • 25
0 votes
1 answer
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 (...
user avatar
  • 25
38 votes
3 answers
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 ...
user avatar
1 vote
0 answers
158 views

Counting states for Peg Solitaire 2^33 != Riemann Sum i = 1, n = 33 (nCi)?

So I have this question that is finding all states (not possible states just states if this game didn't have rules) for a game of Peg Solitaire. For those unaware of what it is: https://www.youtube....
user avatar
  • 477