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 ...
- 14.7k
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^*$: ...
- 393
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 ...
- 38.2k
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=...
- 38.2k
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