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 ?
$\begingroup$
$\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.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. ♦Dec 4, 2017 at 3:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
-
$\begingroup$ see my comment above do you think $|w|$ would have any other meaning ? $\endgroup$– zythonDec 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$– padawanDec 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.Dec 3, 2017 at 21:37