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
0answers
8 views

Valid NFA with minimum number of states for set {0, 1} where each 0 is followed by a 1

Construct a Non-deterministic Finite State Automaton (NFA) with minimum number of states for the set of strings over {0, 1} such that each 0 in the string is immediately followed by a 1. This is the ...
0
votes
1answer
30 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-...
0
votes
0answers
26 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+...
2
votes
2answers
24 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 ...
1
vote
1answer
24 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,...
0
votes
1answer
15 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; ...
0
votes
2answers
40 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 ...
0
votes
2answers
51 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 ...
-1
votes
1answer
77 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\}$ ...
1
vote
1answer
35 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 ...
1
vote
1answer
299 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
vote
0answers
31 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 ...
0
votes
1answer
62 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 ...
1
vote
1answer
52 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 ...
1
vote
1answer
261 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\{...
1
vote
0answers
29 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 ...
0
votes
1answer
162 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, Σ, δ, ...
0
votes
0answers
130 views

Error States in Finite State Machine

When we have a Finite State Machine, what is an error state and how do we implement one? My guess is that it's a state that doesn't have a transition away from it?
0
votes
1answer
298 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 ...
0
votes
1answer
131 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 (...
37
votes
3answers
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 ...
0
votes
0answers
37 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....
4
votes
0answers
57 views

Advanced Math for Reinfrocement Learning - state space and state sequences (policies)

Reinforcement learning has two important notions and I am interested in advanced math that can investigate those notions: State space - set of states. Apparently, deep structures should exist in this ...
-1
votes
1answer
77 views

What would be the transition for ten coins?

There are ten coins and a move is made up of flipping any three adjacent coins: H H T T H T H T H T -> H T H H H T H T H T (flip: 2,3,4). How can this transition be represented? / EG: There are 102 ...
0
votes
1answer
100 views

Markov chain with known duration

Let's say there are 2 states (A & B), where the probability of going from state A to B in interval i is $P_{ab}$. State B always lasts for n intervals, then always goes to back to state A. I ...
0
votes
1answer
32 views

Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply?

Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply? my answer That all languages can be recognized by finite automata. ...
1
vote
2answers
191 views

Pumping lemma, L={WW^R | W can be {1}+}

im trying to find out, if L is regular or not using pumping lemma. I have L={WW^R | W can be {1}+} So possible strings would be 11, 1111, 111111. In every cases i have googled so far are examples ...
1
vote
1answer
46 views

Language of this finite state automaton?

What would be the formal definition of the language for the following Finite State Automaton?
0
votes
1answer
9k views

Conversion of an Epsilon NFA to a DFA

I need to convert this NFA to a DFA, but I only have the method for NFAs without Epsilons: My calculation was: But the expected result is: Is there a process to use for converting this to get the ...
1
vote
1answer
332 views

How to draw a DFA from regular expression a*b*?

I'm doing some exercises to the topic DFA and noticed, that most solutions I could find to a specific language do not look like my own solution to it and I'm kinda confused. The condition of the L is {...
1
vote
2answers
32 views

Showing that a Language is regular using a state machine diagram

I'm in my first few weeks of taking a theoretical course at my school and was wondering what is wrong with my answer to this question. I've been told to show that the language: L = {x | x has even ...
1
vote
4answers
164 views

How do I know if a base-$3$ number is congruent to $3\pmod 5$?

The problem: Professor Martinez needs a state machine that will recognize certain base-$3$ numbers. It should read the digits in left-to-right order. That is, if you’ve seen number $x$ and read a new ...
1
vote
1answer
220 views

First Order Logic knowledge base problem

I would like to present in the predicate logic the knowledge base and then check if the one provided formula is satisfied using the defined knowledgebase. I am trying to do this using SPASS prover, ...
1
vote
2answers
660 views

Creating a deterministic Finite state machine that accepts even 1s parity

Ive been working on this project for over a week now and its coming due soon, and im in no way going to finish it soon. the project is essentially where we have been assigned 3 "Codes" which form a ...
0
votes
1answer
838 views

Turing machine to replace consecutive 1's with 0's

The task at hand is to construct a set of instructions for a Turing machine that changes consecutive (i.e. at substrings of at least two) 1's into 0's, leaving everything else on the tape untouched in ...
1
vote
2answers
61 views

Can formal language theory be correctly characterized as a branch of discrete mathematics?

Can formal language theory be correctly characterized as a branch of discrete mathematics? If so, what is the correct antonym for "discrete" here? Reason I'm asking is that for rhetorical purposes ...
0
votes
0answers
296 views

Modelling a Propositional Formula

Considering the following finite state automata: Finite State Automata Image - 1 Model the transition relation using the formula: model = (a → b') ∧ (b → c') ∧ (c → b') Now, Model as a ...
2
votes
1answer
132 views

if $R \equiv RR$, then $R \equiv \emptyset$ or $\epsilon \in L(R)$

For each of these implications, state whether it holds for arbitrary regular expressions R, S and justify your answer If $R \equiv RR$, then $R \equiv \emptyset$ or $\epsilon \in L(R)$ Solution: $R ...
0
votes
1answer
380 views

How to read FSM diagram?

How do I read this? I have searched everywhere and I don't know how to read it. It is a machine for calculating if a binary number is divisible by 5... apparently... (I don't know how to read it, ...
1
vote
0answers
45 views

Construct Phrase Structure Gammar G

I have the following question, construct the phrase structure grammar G such that the language $L(G)$ is equal to language $L=\{x^n y^m | n \geq 2, m =2k, k\in \mathbb{ N}\}$ From my basic ...
3
votes
2answers
159 views

How math deals with state or “algebra of sequential logic”

Boolean algebra is well-studied and you could easily find a lot of introductory materials on different operators, properties, how eveything is nicely related to the algebra of sets, and so on. Coming ...
1
vote
1answer
214 views

What is the difference between a “Weakly increasing variables” and “not being a decreasing variable”?

I was reading subsection 5.4.6 about state machine derived variables in Mathematics for Computer Science, after defining weakly/strictly increasing and decreasing variables, this was in the footnote. ...
0
votes
1answer
61 views

What are my further steps in creating a deterministic finite automaton?

I have to create a Deterministic finite automaton that handles the regular language (0100 + 0001 + 01)* and has a parity bit at the end to make sure 0's are even. To clarify what I mean by even 0 ...
6
votes
2answers
1k views

Is it possible for a finite state machine to detect if a string has the same number of ones as zeros?

I'm having difficulty with a seemingly simple question. "Is it possible to have a finite state machine that detects if a bit string of arbitrary length has the same number of zeros as ones? If so what ...
0
votes
1answer
383 views

Finite state machine question

How do I find a regular expression for this language, and how do I define a finite state machine that recognizes words in the language (input alphabet, states, start state, state transition table, and ...