= Suffix-nonnegative binary language
{title2=$\{w:\ |v|_0\geq |v|_1\text{ for every suffix }v\text{ of }w\}$}
A <context-free language> recognized by scanning a <string> over the <alphabet> $\{0,1\}$ from right to left, counting 0 as $+1$ and 1 as $-1$, and requiring every partial count to remain nonnegative. A <context-free grammar> with a unique <parse tree> for each generated <string> is $S\to\epsilon\mid S0\mid S1B0$, $B\to\epsilon\mid B1B0$. To see uniqueness, reverse the <strings>: every nonempty nonnegative path either never returns to zero after its first step, or has a unique first return. These two cases determine the production and its component substrings.
Back to article page
