# Questions tagged [finite-state-machine]

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

74 questions
Filter by
Sorted by
Tagged with
24 views

1 vote
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?
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}$ ...
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 ...
1 vote
114 views

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 ...
1 vote
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,...
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; ...
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 ...
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 ...
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\}$ ...
1 vote
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 ...
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 vote
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 ...
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 ...
1 vote
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 ...
1 vote
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\{...
1 vote
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 ...
1 vote
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, Σ, δ, ...
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 ...