Skip to main content

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
30 views

Construction of a Finite State Automaton given a grammar

I have been studying formal language and automata theory from Mathematical Methods in Linguistics (Partee et al.). Specifically, I have been learning about finite state automata, formal languages, and ...
blanchietz's user avatar
1 vote
0 answers
45 views

State Diagram in Finite State Machines

This question is in Grimaldi's book: Let $I$ = $o$ = {0, 1}. Construct a state diagram for a finite state machine that recognizes each occurrence of $1010$ in a string x $\in$ $I^*$. (Here overlapping ...
winter's user avatar
  • 63
0 votes
0 answers
21 views

Converting generalized nondeterministic finite automata (GNFA) into regular expressions

When converting from a GNFA to a regular expression, we systematically remove states from the GNFA until we are left with just the start and accept state such that the transition arrow from the former ...
Michael24601's user avatar
0 votes
1 answer
63 views

The state machine for "Extended Euclidean Gcd Algorithm" terminates after at most the same number of transitions as that of the Euclidean algorithm

This is one following question based on one question I asked before In spring18 mcs.pdf, it has Problem 9.13: Define the Pulverizer State machine to have: $$ \begin{align*} \text{states} ::=&...
An5Drama's user avatar
  • 416
0 votes
1 answer
58 views

Why is the Pulverizer machine partially correct?

In spring18 mcs.pdf, it has Problem 9.13: Define the Pulverizer State machine to have: $$ \begin{align*} \text{states} ::=& \mathbb{N}^6&\\ \text{start state} ::=& (a, b, 0, 1, ...
An5Drama's user avatar
  • 416
1 vote
2 answers
84 views

Show that, if $L$ is a regular language, then so is $\{w : \exists n \in \Bbb{N}, w^n \in L\}$

Suppose $L$ is a regular language over an alphabet $\Sigma$. Let $$L' = \{w : \exists n \in \Bbb{N}, w^n \in L\}.$$ Prove that $L'$ is regular too.
Theo Bendit's user avatar
  • 51.8k
1 vote
1 answer
61 views

States and Probability

In a game of croquet, a ball begins at Wicket A. On a given move, a ball struck from Wicket A has a $\dfrac{1}{2}$ chance of staying at Wicket A and a $\dfrac{1}{2}$ chance of going to Wicket B. On a ...
John Doe 's user avatar
0 votes
0 answers
26 views

Issue Solving States/Markov Chain Problem

Problem: We have a bowling ball and a lane that is 50 meters long and 2.5 meters wide and is surrounded by 50 meter long gutters on both sides. For every meter forward that the ball travels, given ...
John Doe 's user avatar
0 votes
0 answers
30 views

Build a tree of outputs with numbered vertices and edges

I am trying to understand this task that is related to Deterministic functions, Moore diagrams, and canonical equations which requires several requirements. We have this equation $y(k) = \{x(1), x(2) →...
Abdullatif Frxan's user avatar
1 vote
0 answers
71 views

Can substrings of a regular language always be recognized by an "isolated" path in some finite state automaton?

I believe I have found a proof of the question I originally asked (see crossed out paragraph), but I have realized that what I actually need to prove is somewhat stronger. What I am actually wondering ...
M. Sperling's user avatar
2 votes
1 answer
59 views

Programmer struggling to navigate through mathematics notation and formulas(AI)

I'm a programmer and I've studied some calculus and linear algebra years ago. I've been getting in to AI recently and I struggle understanding some of the mathematical notation and formulas. I ...
danial javady's user avatar
1 vote
0 answers
590 views

Finite state machine which only accepts binary strings with an odd number of zeros

I want to create a finite state machine that takes strings with only 0 and 1 as input. The finite state machine shall only accept strings with an odd number of zeros and the sum of the numbers in the ...
Tommy's user avatar
  • 19
0 votes
0 answers
15 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 ...
RandomDeveloper's user avatar
2 votes
1 answer
215 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 ...
languagen00b's user avatar
0 votes
0 answers
111 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 ...
liz's user avatar
  • 1
3 votes
1 answer
327 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? ...
Marx's user avatar
  • 33
0 votes
1 answer
77 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 ...
Ben Harris's user avatar
1 vote
1 answer
34 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 ...
Raj Raina's user avatar
  • 1,049
1 vote
1 answer
63 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 ...
Trevor's user avatar
  • 6,014
1 vote
0 answers
19 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. ...
LRDPRDX's user avatar
  • 1,288
1 vote
0 answers
13 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 ...
Bula's user avatar
  • 181
1 vote
2 answers
237 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$ ...
c4ristian's user avatar
5 votes
0 answers
395 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 ...
PanJanek's user avatar
  • 169
0 votes
0 answers
329 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-...
Yoav's user avatar
  • 1
0 votes
0 answers
568 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 ...
Shubham Agrawal's user avatar
1 vote
2 answers
256 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 ...
Peter Staudt's user avatar
1 vote
1 answer
80 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/...
milad's user avatar
  • 133
0 votes
1 answer
30 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 ...
pumping_until_swole's user avatar
4 votes
1 answer
89 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 $\...
mathreadler's user avatar
  • 26.1k
1 vote
1 answer
42 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?
postFix's user avatar
  • 275
0 votes
2 answers
295 views

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

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}$ back to $q_{0}$ did not exist, the probability ...
Mr. Yak's user avatar
  • 13
2 votes
1 answer
206 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 ...
milin's user avatar
  • 223
1 vote
1 answer
121 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) \...
JustAsking's user avatar
0 votes
1 answer
216 views

Calculating a transition probability in FSM

I have a Finite State Machine represented in following form: ...
Ach113's user avatar
  • 103
3 votes
0 answers
288 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]^*$...
AFC's user avatar
  • 383
1 vote
1 answer
112 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 ...
GratefulGuest's user avatar
0 votes
0 answers
15 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 ...
Ettore's user avatar
  • 537
0 votes
1 answer
240 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-...
Apoorv Jain's user avatar
1 vote
0 answers
328 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+...
qwerty_99's user avatar
  • 113
2 votes
2 answers
144 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 ...
Daphoa's user avatar
  • 21
1 vote
1 answer
107 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,...
quantumferret's user avatar
0 votes
1 answer
52 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; ...
Anonymous Goose's user avatar
0 votes
2 answers
261 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 ...
Deep_Television's user avatar
0 votes
2 answers
101 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 ...
NimaJan's user avatar
  • 290
-1 votes
1 answer
90 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\}$ ...
NimaJan's user avatar
  • 290
1 vote
1 answer
95 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 ...
Andy's user avatar
  • 11
3 votes
1 answer
5k 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 ...
Sprinkle's user avatar
  • 1,176
1 vote
0 answers
121 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 ...
Sam Walko's user avatar
0 votes
1 answer
366 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 ...
Jeffrey D's user avatar
1 vote
1 answer
56 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 ...
Joshua Anderson's user avatar