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
39 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-...
0
votes
0answers
23 views

How do I convert the following NFA to a DFA?

From my textbook, I am trying to convert the above NFA to a DFA (no solution provided). I went through the steps to convert it and ended up with the following DFA solution: At first glance, I thought ...
1
vote
0answers
19 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
2answers
22 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 ...
1
vote
1answer
50 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/...
0
votes
1answer
24 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
1answer
78 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 $\...
1
vote
1answer
22 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?
0
votes
2answers
40 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}$ ...
2
votes
1answer
96 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
1answer
52 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) \...
0
votes
0answers
15 views

Minimize the finite state machine given by the following state table

Minimize the finite state machine given by the following state table
1
vote
1answer
24 views

Calculating a transition probability in FSM

I have a Finite State Machine represented in following form: ...
3
votes
0answers
67 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]^*$...
1
vote
1answer
48 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 ...
0
votes
0answers
12 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 ...
0
votes
1answer
93 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-...
1
vote
0answers
81 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
32 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
54 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
19 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
80 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
58 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
84 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
42 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
2k 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
43 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
105 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
53 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
718 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
36 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
1answer
385 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
1answer
710 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
244 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 (...
38
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 ...
1
vote
0answers
65 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
59 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
112 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
36 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
397 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
54 views

Language of this finite state automaton?

What would be the formal definition of the language for the following Finite State Automaton?
1
vote
1answer
14k 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
473 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
36 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
499 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 ...
2
votes
1answer
245 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
882 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 ...
1
vote
1answer
1k 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
65 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 ...