Questions tagged [finite-state-machine]
For questions about finite state machine, which is a mathematical model of computation.
74
questions
0
votes
0
answers
24
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) →...
1
vote
0
answers
27
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 ...
- 353
0
votes
0
answers
30
views
What is the purpose a 1,0 or 0,1 loop at the end of the language DFA?
Here is a finite-state automata without output:
Language recognition automata without output
In finite-state machine with output, I understand that the 1,0 or 0,1 would give an output of 0 if input is ...
0
votes
0
answers
25
views
General Rules for finding FSA/DFA
I am currently taking a course of Finite State Automata, Deterministic Finite Automata, etc.
However, I can't seem to understand if there is a systematic way to solve any FSA/DFA given to me in class. ...
2
votes
1
answer
51
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 ...
1
vote
0
answers
184
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 ...
- 19
0
votes
0
answers
12
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 ...
- 101
2
votes
1
answer
134
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 ...
- 23
0
votes
0
answers
76
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
3
votes
1
answer
187
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
0
votes
1
answer
69
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 ...
- 21
1
vote
1
answer
33
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 ...
- 999
1
vote
1
answer
50
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,698
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.
...
- 1,278
1
vote
0
answers
12
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 ...
- 181
1
vote
2
answers
211
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$ ...
- 63
5
votes
0
answers
363
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 ...
- 169
0
votes
0
answers
253
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
0
votes
0
answers
383
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
2
answers
217
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 ...
- 514
1
vote
1
answer
70
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
0
votes
1
answer
28
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 ...
4
votes
1
answer
82
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 $\...
- 25.4k
1
vote
1
answer
38
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?
- 257
0
votes
2
answers
204
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}$ ...
- 13
2
votes
1
answer
180
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 ...
- 223
1
vote
1
answer
114
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) \...
- 297
1
vote
1
answer
177
views
Calculating a transition probability in FSM
I have a Finite State Machine represented in following form:
...
- 113
3
votes
0
answers
205
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
1
answer
95
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 ...
- 131
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 ...
- 487
0
votes
1
answer
218
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
0
answers
269
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+...
- 113
2
votes
2
answers
126
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 ...
- 21
1
vote
1
answer
81
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,...
- 133
0
votes
1
answer
50
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; ...
- 179
0
votes
2
answers
214
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 ...
- 771
0
votes
2
answers
70
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 ...
- 290
-1
votes
1
answer
88
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\}$ ...
- 290
1
vote
1
answer
72
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 ...
- 11
3
votes
1
answer
4k
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 ...
- 1,101
1
vote
0
answers
79
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 ...
- 11
0
votes
1
answer
328
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 ...
- 91
1
vote
1
answer
55
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 ...
- 301
1
vote
1
answer
2k
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\{...
- 301
1
vote
0
answers
43
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 ...
- 127
1
vote
1
answer
465
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
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 ...
- 25
0
votes
1
answer
314
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
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 ...
- 370