# What does $|w|$ mean in the statement “ $|w|$ where $w \in L \subset \Sigma^*$”?

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 ?

• 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.) – Sora. Dec 3 '17 at 22:12
• 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! – D.W. Dec 4 '17 at 3:30

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$.

• see my comment above do you think $|w|$ would have any other meaning ? – zython Dec 3 '17 at 18:58
• 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. – padawan Dec 3 '17 at 19:02
• @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$. – Sora. Dec 3 '17 at 21:37