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{...
- 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^*$$
- 10.3k
Only top scored, non community-wiki answers of a minimum length are eligible