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
    $\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. Dec 3 '17 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. Dec 4 '17 at 3:30
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$
  • $\begingroup$ see my comment above do you think $|w|$ would have any other meaning ? $\endgroup$ – zython Dec 3 '17 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 Dec 3 '17 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. Dec 3 '17 at 21:37

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.