Library

PFA · Stochastic

Classic: Rabin's cut-point language

@thethinkmachine·version 1·CC BY 4.0·added 28 Sept 2026

The accepting mass after w is the binary fraction 0.wᴿ. With cut-point 0.5 the machine accepts exactly the words whose reversed binary value exceeds one half.

Open in AutomataStudio
More
Open in the desktop app Download the .automaton file Source on GitHub
q0q10, 1100, 1
The machine as drawn — 2 states, 6 transitions.

The author’s examples, run

0 → reject1 → reject11 → accept01 → reject10 → reject111 → accept