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.'s user avatar
  • 154k
2 votes

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{...
Rémi's user avatar
  • 86
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^*$$
Yves Daoust's user avatar
  • 10.3k

Only top scored, non community-wiki answers of a minimum length are eligible