I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language.

$Σ \in \{a,b\}$

$L = \{ w \in Σ^*\, |\, |w| \equiv 2 \mod 3 \} $

I already solved tasks of that kind, but now i struggle to understand what $|w| \equiv 2 \mod 3$ means. $|w|$ means the length of $w$ right? Does $\equiv 2 \mod 3$ mean that $|w|$ should be $2$ (because 2 modulo 3 is 2)?

  • 1
    $\begingroup$ Note that this is a pure mathematics question (the context of formal languages is rather irrelevant) so you should have posted it to Mathematics. $\endgroup$
    – Raphael
    Nov 3, 2017 at 12:14
  • $\begingroup$ But if he did not completely understand the mod notation, how could he be sure that it is more about mathematics than CS, @Raphael ? And he also asked about |w| (yes, only for reassurance), which is clearly formal languages. $\endgroup$ Nov 3, 2017 at 12:31
  • $\begingroup$ @PeterLeupold Raphael is informing, not blaming. Obviously, if the asker had known that their question is better-suited to another site, they would have posted it there rather than here. $\endgroup$ Nov 3, 2017 at 17:05

1 Answer 1


Yes, $|w|$ is the length of $w$.

So $|w| \equiv 2 \mod 3$ means that the length of w divided by three should have the remainder 2. It should be from the set $\{2, 5, 8, \dots\}$.


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.