New answers tagged finite-automata
7
votes
Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language
One way to look at these specific problems is to have states labeled $(x,y)$ where $x$ will correspond to the ones seen so far and $y$ similarly to the zeros so far. These are taken mod 2 or mod 3 ...
4
votes
Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language
There is a general approach, though I am not sure knowing it is of practical use. Fix an alphabet $\Sigma$ and let $L$ be a regular language. Define the following equivalence relation on $\Sigma^*$: ...
1
vote
Accepted
Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$
Yes, the number of states in $A$ at level $n$ is $p$, even without the 3rd constraint. The following is a proof.
Assume $A$ is constructed as in this answer.
As observed in question, it is ...
3
votes
Accepted
Does my finite state automaton accept a string iff it contains the given string as a substring?
Remarks on your FSA
Your specification of the FSA is
not finished. The transitions from states other than $q_n$ where the symbol read is not in $S$ are not defined.
ambiguous.
What happens if $s_1=...
1
vote
Exactly what is the difference between Finite Automata and Transition Graphs?
TL;DR version:
Your initial statement was accurate - I'll add some more clarity (hopefully) for people who come across this post later on:
The formal definition (from Daniel I.A. Cohen):
A transition ...
1
vote
Accepted
Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$
Yes, and yes. This follows from the result in your prior question, letting $L = L_1 \cup L_2$ or $L = L_1 \cup \dots \cup L_p$.

D.W.♦
- 152k
Top 50 recent answers are included
Related Tags
finite-automata × 1711automata × 788
regular-languages × 524
formal-languages × 318
regular-expressions × 282
nondeterminism × 139
turing-machines × 80
pumping-lemma × 65
algorithms × 60
context-free × 58
pushdown-automata × 58
computability × 55
closure-properties × 52
complexity-theory × 51
formal-grammars × 48
computation-models × 40
proof-techniques × 33
compilers × 29
reference-request × 22
simulation × 21
terminology × 20
undecidability × 20
transducers × 16
graphs × 14
strings × 14