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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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