0
$\begingroup$

This question already has an answer here:

Suppose the language L = {w | w is an integer whose sum of digits is a multiple of 2}. I strongly feel like this is non-regular language, but how should I choose a string to apply the pumping lemma?

$\endgroup$

marked as duplicate by David Richerby, Raphael Oct 21 '17 at 20:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Remember that a language is regular iff it is in SPACE(O(1)). $\endgroup$ – quicksort Oct 21 '17 at 9:04
3
$\begingroup$

The language $L$ is regular as shown by the following "flip-flop" style minimal and deterministic automaton $\mathcal{A}$, the crux is that you need only two states (not an unbounded amount of memory) to check parity. $\mathcal{A} = \langle \{odd,even\}, \{0..9\}, even, \{even\}, \delta \rangle$ which transition function $\delta$ is defined by :

  • $\delta(x,even) = even$ when $x\in \{0,2,4,6,8\}$
  • $\delta(x,even) = odd$ when $x\in \{1,3,5,7,9\}$
  • $\delta(x,odd) = even$ when $x\in \{1,3,5,7,9\}$
  • $\delta(x,odd) = odd$ when $x\in \{0,2,4,6,8\}$
$\endgroup$
  • $\begingroup$ Why is it that the automaton would fail in the case you mentioned? Also, what do you mean by fail? I think I must be overlooking something. $\endgroup$ – Odo Frodo Oct 21 '17 at 17:50
  • $\begingroup$ The last sentence was added. I dont understand it either. $\endgroup$ – Romuald Oct 21 '17 at 17:57
  • $\begingroup$ As far as I can see, the added sentence was wrong. I deleted it. You should always feel free to undo edits to your own posts that you think are wrong. $\endgroup$ – David Richerby Oct 21 '17 at 19:56

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