1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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, 2019 at 2:22

1 Answer 1

Reset to default
0
$\begingroup$

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$,

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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