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 '17 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$ – Peter Leupold Nov 3 '17 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$ – David Richerby Nov 3 '17 at 17:05

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, privacy policy and cookie policy

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