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: enter image description here

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.

  • $\begingroup$ 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? $\endgroup$ – 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$,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.