What is the Monodic Second Order formula that encodes all binary strings that represent a valid parenthesis matching ? By this I mean 1s represent '(' and 0s represent ')' and at every position, number of 1s in the prefix is greater than or equal to the number of 0s .
Can someone tell me how to proceed ?
Thanks!
Hint. MSO captures exactly the regular languages.