โ† Theory of Computation learning path
Theory of Computation ยท Module 1 of 10

Alphabets, strings and languages

The vocabulary of automata theory.

๐Ÿ“– Key ideas

  1. An alphabet (Sigma) is a finite set of symbols, such as {0, 1}.
  2. A string is a finite sequence of symbols; epsilon is the empty string of length 0.
  3. A language is a set of strings over an alphabet, finite or infinite.
  4. Sigma* is the set of all strings including epsilon; Sigma+ excludes epsilon.
  5. Operations on languages: union, concatenation and Kleene star.
๐Ÿ’ก Real-life example: An alphabet is like the letters of English, strings are words built from them, and a language is a dictionary that lists which words are allowed.
AlphabetFinite set of symbols
EpsilonEmpty string of length zero
LanguageSet of strings over an alphabet
Kleene starZero or more concatenations of strings from a language