2
$\begingroup$

In my assignment I find these symbols:

$|w|$ where $w \in L \subset \Sigma^*$

I believe it means the lexikografic value of a word, but I am not 100% certain.

Let me phrase my question this way: could this notation have any other meaning ?

$\endgroup$
2
  • 2
    $\begingroup$ It almost certainly means the length of the word $w$. (But I'm sure you will find the definition in your lecture notes or textbooks. It's a long shot, but since you're from Germany - if your textbook is "Theoretische Informatik - kurz gefasst", have a look at the last paragraph of p. 177.) $\endgroup$
    – Sora.
    Commented Dec 3, 2017 at 22:12
  • 2
    $\begingroup$ For the future: I encourage you to edit your question to clarify it (rather than leaving a comment with a clarification). We want questions to stand on their own, so that people can understand what you are asking without having to read the comments. Thank you! $\endgroup$
    – D.W.
    Commented Dec 4, 2017 at 3:30

1 Answer 1

4
$\begingroup$

Usually, $\Sigma^*$ denotes the set of all strings obtainable from an alphabet $\Sigma$.

Most probably, $L$ is a language and $w$ is a word. A language is a subset of the alphabet $\Sigma^*$, thus $L \subset \Sigma^*$.

A word, on the other hand, is a single string obtained from the language $L$.

As an example:

$\Sigma = \{0,1\}$
$\Sigma^* = \{0, 01, 10, 11, 100, 101, \dots, 1011001001, \dots\}$
$L \gets$ all strings containing an even number of zeroes
$w \gets 100010$

And $|w|$ is probably the length of $w$.

$\endgroup$
3
  • $\begingroup$ see my comment above do you think $|w|$ would have any other meaning ? $\endgroup$
    – zython
    Commented Dec 3, 2017 at 18:58
  • 1
    $\begingroup$ Actually, $w \in L \subset \Sigma^*$ is mathematically imprecise. First of all, it should be $L \subseteq \Sigma$. And moreover, different operations should are not transitive i.e. writing "element of" and "subset of" in the same statement makes it kind of ambigious. Other than that, I would not say it can carry any other meaning unless stated otherwise. $\endgroup$
    – padawan
    Commented Dec 3, 2017 at 19:02
  • 4
    $\begingroup$ @padawan I beg to differ - first, using $\subset$ to denote what may or may not be a proper subset is far from unusual (but it depends on the author) - it would become a problem only if $\subsetneq$ had been used. Second, statements of the form $a\in A\subset B$ are often seen as an abbreviation of "$a\in A$ and $A\subset B$", there is no ambiguity to it - by the definition of $A\subset B$, which is $x\in A\ \Rightarrow\ x\in B$, $a$ is an element of both, but it is clear from the way it's written that $a\in A$ is implied, not $a\in B\setminus A$. $\endgroup$
    – Sora.
    Commented Dec 3, 2017 at 21:37

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.