Content deleted Content added
→Lexicographical ordering: give a counter-example for well-ordering |
HeyElliott (talk | contribs) |
||
Line 257:
The ''[[length]]'' of a string ''s'' is the number of symbols in ''s'' (the length of the sequence) and can be any [[non-negative integer]]; it is often denoted as |''s''|. The ''[[empty string]]'' is the unique string over Σ of length 0, and is denoted ''ε'' or ''λ''.<ref name="partee"/><ref>{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}} Here: sect.1.1, p.1</ref>
The set of all strings over Σ of length ''n'' is denoted Σ<sup>''n''</sup>. For example, if Σ = {0, 1}, then Σ<sup>2</sup> = {00, 01, 10, 11}.
The set of all strings over Σ of any length is the [[Kleene star|Kleene closure]] of Σ and is denoted Σ<sup>*</sup>. In terms of Σ<sup>''n''</sup>,
| |||