Suffix-nonnegative binary language
ID: suffix-nonnegative-binary-language
A context-free language recognized by scanning a string over the alphabet from right to left, counting 0 as and 1 as , and requiring every partial count to remain nonnegative. A context-free grammar with a unique parse tree for each generated string is , . 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.
New to topics? Read the docs here!