# MSO (Monadic second-order logic) Logic On Words

Let L be a language over $$\Sigma = \{a,b,c\}$$ that contains all words, where the length $$|w|_b$$ (number of all b's) has remainder 1 if divided by 3.

MSO logic over words are definded as follow:

I want to express this language using MSO logic. But my problem is how can I count the b's to calculate the reminder? So it would be easiert if I just look on $$|w|$$, cause I could use max.

• The situation you described happens to be a typical example of a language that can be recognized by a deterministic finite automata. Is there a way to translate DFAs into MSOs? – Display Name May 16 at 2:22

Start with the following: There are three disjoint sets $$X_1,X_2,X_0$$ that together hold the $$b$$-positions of the string. The last $$b$$ is in set $$X_1$$,