1
$\begingroup$

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?

$\endgroup$
2
  • 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$ Feb 2, 2016 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, 2016 at 14:05

3 Answers 3

8
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

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

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.

$\endgroup$
5
  • $\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$ Feb 3, 2016 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, 2016 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$ Feb 4, 2016 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, 2016 at 21:55
  • $\begingroup$ Yes, absolutely. $\endgroup$ Feb 4, 2016 at 22:21

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.