1
$\begingroup$

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

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

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.

$\endgroup$

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.