3
votes
Translating non-deterministic finite automata with counters to deterministic ones
Yes, they can be employed in a straightforward way. However, the size of the formulas blows up exponentially big.
Let $\ell_{s \to t}$ denote the formula on the NFA transition from $s$ to $t$. For ...

D.W.♦
- 154k
2
votes
Accepted
State Machines as Functors
A very similar construction/viewpoint has been recently studied by Colcombet and Petrişan in [CP20]. They see a deterministic finite automaton as a functor
$$\mathcal{A} \colon \mathcal{I} \to \mathsf{...
1
vote
Regular expression for binary string containing no instances of 01
If there is a $0$, it may not be followed by a $1$, so the string is made of "not $0$s" followed by $0$s.
$$1^*0^*$$
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
automata × 1762finite-automata × 794
formal-languages × 437
regular-languages × 365
pushdown-automata × 227
context-free × 219
regular-expressions × 184
turing-machines × 165
nondeterminism × 104
formal-grammars × 98
computability × 79
computation-models × 59
pumping-lemma × 55
complexity-theory × 45
algorithms × 43
closure-properties × 41
undecidability × 39
terminology × 31
compilers × 31
reference-request × 30
simulation × 29
proof-techniques × 27
parsers × 23
buchi-automata × 19
reductions × 16