# Questions tagged [finite-state-machine]

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

80 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
• 63
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 ...
63 views

• 416
1 vote
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.
• 51.8k
1 vote
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 ...
• 111
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 ...
• 111
30 views

• 26.1k
1 vote
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?
• 275
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 ...
• 13
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 ...
• 223
1 vote
121 views

• 113
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 ...
• 21
1 vote
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,...
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; ...
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 ...
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 ...
• 290
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\}$ ...
• 290
1 vote
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 ...
• 11
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 ...
• 1,176
1 vote
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 ...
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 ...
$$\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 ...