There is this example of regular expressions:

$$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$

From that I understand the empty string is valid as a string of even length. Is this true?

  • 2
    $\begingroup$ Of course zero is even: it is two times zero. By the way: isnt there one $\Sigma$ too much in the expression? $\endgroup$ – Hendrik Jan Feb 2 '16 at 5:12
  • $\begingroup$ Ah ok I wasn't even thinking about zero. Nope that's the right number of $\Sigma$. $\endgroup$ – Brian Feb 2 '16 at 14:05

A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.


Even number - Even number = even number.
Odd number - odd number = even number.
0 - 0 = 0
Since it cannot change parity it must be even.

Furthermore 0's neighbours are odd, which also implies it is even (as every second number has the same parity).
Zero parity

  • 1
    $\begingroup$ What does advice on checking the parity of a number using bitmasks have to do with the question? $\endgroup$ – Tom van der Zanden Feb 2 '16 at 8:12
  • $\begingroup$ Might as well explain the whole number theory. $\endgroup$ – PleaseHelp Feb 2 '16 at 8:40

Yes, that's correct. Empty string is valid as string of even length.

If you consider any language of even length of strings, it will also include an empty string.So, it is true.

  • $\begingroup$ "If you consider any language having even length of strings, it will also include an empty string." That's not true. For example, the language of all strings over $\{0,1\}$ that have even length and contain the string $000$ is a language of even-length strings that doesn't include $\epsilon$ (or any other string of length less than four). $\endgroup$ – David Richerby Feb 3 '16 at 19:30
  • $\begingroup$ @DavidRicherby I meant this ' All the languages of even length strings(but don't contain strings other than even length strings ) include empty strings too.' Edit has been done. :) $\endgroup$ – Parth S. Feb 4 '16 at 12:49
  • $\begingroup$ But it's not true that all languages of even length strings include the empty string! I just gave you an example showing that that's false. $\endgroup$ – David Richerby Feb 4 '16 at 15:34
  • $\begingroup$ @DavidRicherby so can we say that the language of all even length strings including null contains empty string? $\endgroup$ – Parth S. Feb 4 '16 at 21:55
  • $\begingroup$ Yes, absolutely. $\endgroup$ – David Richerby Feb 4 '16 at 22:21

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.