see also in programming string (C)
- an alphabet \(\Sigma\) is a finite set
- a finite-sequence of elements in \(\Sigma\) is called a string
- the set of all strings in \(\Sigma\) is called \(\Sigma^{*}\), which includes the empty string
- for a particular string \(x\), the length of it is \(|x|\)
- the string of length zero is called \(\varepsilon\)
- a language is a subset of \(\Sigma^{*}\), meaning its a set of strings
Omer seems to call strings “words” sometimes.
languages are boolean function over strings
For every language \(L\) over \(\Sigma\) corresponds to a unique function \(f: \Sigma^{*} \to \{0,1\}\), whereby if \(f(x) = 1\), then \(x \in L\); otherwise, if \(f(x) = 0\), \(x \not \in L\).