Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [finite-state-machine]

The tag has no usage guidance.

-1
votes
1answer
27 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
66 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
14 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. ...
0
votes
0answers
33 views

State-elimination on FSA, after epsilon-removal construction

I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression. But there are already some epsilon ...
1
vote
2answers
64 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
37 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
1k 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
132 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
30 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
79 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
141 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
276 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
418 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
53 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
263 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
108 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
205 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
35 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
115 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
63 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
53 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
780 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
333 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 ...