# Find the grammar for the given language

$L = \{ w: |w| \bmod 3 \geq |w| \bmod 2 \}$

I know, when the length of strings is not $3, 9, 15, 21,\dots,$ they will be members of the given language but unable to write a grammar for this language.

Please confirm one more thing, that this given language is regular?

• In fact, it should be all strings excluding those with length 3, 9, 15, 21, ..., – fade2black Aug 31 '17 at 22:46
• Hint: construct a finite automaton. – Raphael Aug 31 '17 at 22:51
• – Raphael Aug 31 '17 at 22:52
• Hint: Use Myhill-Nerode to verify that the language is, indeed, regular. – Raphael Aug 31 '17 at 22:53
• yes, it is regular and DFA for this language will have 12 states. – Manu Thakur Sep 1 '17 at 3:49

Note that this language excludes all strings of length divisible by 3 but not by 2, i.e., of length $3, 9, 15, 21,\dots$.
Consider languages $$L_1 = \{w\mid |w|=2k, k\geq 0\}$$ and $$L_2 = \{w\mid |w|=3k, k\geq 0\}$$ They are regular, since it is very easy to design DFA for both languages; the first has three states, the second has four states. The complement of the language $L$ is equal to $L_2-L_1$, and by the closure properties of regular languages $L=\overline{L_2-L_1}$ is also regular.