As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [finite-automata]

Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

1,702 questions
Filter by
Sorted by
Tagged with
26 views

### Constructing product automaton with conjunctive conditions

The question was to construct a DFA which accepts the language $$\{ x \in \{0,1\}^* \mid x\text{ starts with a }0\text{ and has at most one }1\}$$ So I first constructed DFA for '$x$ starts with a $0$'...
• 105
1k views

### NFA: How does it function with empty-string moves?

How does the NFA function on $\epsilon$ input if there is only a single $\epsilon$ string in the language? I understand that $L^* = \bigcup_{i=0}^\infty L^i$ where $L^0 = \{()\} = \{\epsilon\}$ and $L$...
• 175
309 views

### How to build a deterministic finite automaton from a given one with a new definition for automaton language?

I was given a new definition for a language of an automaton. A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at ...
• 261
89 views

### Description of an automaton

i'm a student and i've been searching the language description of this automaton. The states are as follows: Q = {q1, q2, q3,q4} The alphabet is as follows: Σ = {0,1} The start state is q1 The ...
170 views

• 105
1 vote
237 views

1k views

### Automaton for telling whether a binary number is a multiple of 3

I am designing an automaton which determines whether a binary number is divisible by 3: $$\{x \in \{0, 1\}^* \mid \text{x represents a multiple of three in binary} \}$$ 0 1 0F 0 1 1 2 0 2 1 2 ...
253 views

### A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

I am confused by the following claim: Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
• 171
1 vote
32 views

• 23
1k views

### Proof that for 2n nodes of +1 and -1 position doesn't count

I'm having a hard time understanding how to solve this problem for my Computer Science 101 class. On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a ...
• 225
1 vote
44 views

I was trying to minimize given DFA: a b -> 1 4 2 F 2 1 1 3 1 4 F 4 1 1 I've watched few videos about solving this problem and decided to use the equivalance method. While doing it I've come ...
265 views

### How do we decide whether or not to accept $\epsilon$ in dfa?

Can I exclude $\epsilon$? Will that make a difference. This is really confusing me. It seems everything could contain $\epsilon$. Is there some way of thinking to realize this contains $\epsilon$ or ...
• 37
73 views

### How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
• 866