Content deleted Content added
Jason Quinn (talk | contribs) →Formal theory: removing false statement. There ARE assumptions about the symbols, namely that they are distinct and unambiguous. |
Jason Quinn (talk | contribs) →Formal theory: added expression with Shoenfield reference |
||
Line 252:
{{See also|Tuple}}
Let Σ be a [[finite set]] of distinct, unambiguous symbols (alternatively called characters), called the [[Alphabet (formal languages)|alphabet]]. A '''string''' (or '''word''' or '''expression'''<ref>{{cite book |last=Shoenfield |first=Joseph R. |authorlink=Joseph R. Shoenfield |year=2010 |origyear=1967 |title=Mathematical Logic |edition=Reprint |publisher=CRC Press |isbn=978-156881135-2 |page=2 |quote=Any finite sequence of symbols of a language is called an ''expression'' of that language.}}</ref>) over Σ is any finite [[sequence]] of symbols from Σ.<ref name="partee">{{cite book |author1=Barbara H. Partee |author2=Alice ter Meulen|author2-link=Alice ter Meulen |author3=Robert E. Wall |title=Mathematical Methods in Linguistics |publisher=Kluwer |year=1990}}</ref> For example, if Σ = {0, 1}, then ''01011'' is a string over Σ.
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>
| |||