Questions tagged [finite-state-machine]
For questions about finite state machine, which is a mathematical model of computation.
84 questions
0 votes
0 answers
44 views
Algorithm that determines if an input string is in the language
In a practice midterm question, there's the following question. I am confused about why can't we just return the negation of the output of the FSA, instead of converting it into a Turing Machine. (d) ...
- 21
2 votes
0 answers
60 views
How to derive a procedure to perform bitwise OR between two regular expressions
I was given this problem on regular languages, which I solved, but I was wondering there is another, more elegant way to approach it. I'll share the problem first, along with my solution, and then ...
- 33
0 votes
2 answers
87 views
When do we specify domains when it's implied?
I asked an AI about the language a^m b^n c^n d^m, and in replying to me, it translated that into $\{a^mb^nc^nd^m \mid m, n \geq 0\}$. Is this standard usage? I find it weird; negative integers make no ...
- 123
0 votes
0 answers
71 views
How do I show $p\equiv q$ for states $p,q$ of a DFSM?
Is my following approach correct? What I need to prove: Given $p$ and $q$ are any $2$ states of an arbitrary DFSM, $M$; to prove $p≡q$, I must show $p≡ₙq$ for any natural number $n$. That is, I must ...
- 1
0 votes
0 answers
73 views
Are mathematical proofs basically graphs?
Coming from an algorithmic/programming point of view, are mathematical proofs basically directed graph traversals, or more precisely, finite state machines? Typical structure of mathematical ...
- 456
1 vote
0 answers
63 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 ...
- 63
1 vote
0 answers
142 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 ...
- 11
0 votes
1 answer
143 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} ::=&...
- 456
0 votes
1 answer
197 views
Why is the Pulverizer machine partially correct?
From Eric Lehman et al.'s Mathematics for Computer Science [PDF]: Problem 9.13. $\,$ Define the Pulverizer state machine to have: $$ \begin{align*} \text{states} ::=& \mathbb{N}^6&\\ \...
- 456
1 vote
2 answers
257 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.
- 53.8k
1 vote
1 answer
90 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 ...
- 111
0 votes
0 answers
39 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 ...
- 111
0 votes
0 answers
39 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
114 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 ...
- 807
3 votes
1 answer
68 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 ...
