New answers tagged

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 ...
Rick Decker's user avatar
  • 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^*$: ...
Cactus Golov's user avatar
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 ...
John L.'s user avatar
  • 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=...
John L.'s user avatar
  • 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 ...
John Baugh PhD's user avatar
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.'s user avatar
  • 152k

Top 50 recent answers are included