the central concepts of automata theory

• ALPHABET

  Alphabet (usually represented by Σ) is a non-empty finite set of symbols:

  • Σ = {0,1} ,binary alphabet
  • Σ= {a,b,... z} , set of lower-case letters
  • Set of ASCII chars
• STRING

  String is a finite sequence of symbols over an alphabet: (E.g., 01101 is a string over Σ = {0,1})
• STRING

  Empty string ( ) has zero occurrences of symbols (can be chosen from any alphabet)
• STRING

  Length of a string is the number of symbols over Σ : |01101|= 5, |ξ|= 0
• STRING

  xy denotes the concatenation of the string x and y

  • if x is the string composed i symbols x = a1a2...ai, and y is the string composed of j symbols y = b1b2...bj, then xy is the string of length i + j: xy = a1a2...aib1b2...bj
• STRING

  Power of an alphabet Σk is the set of strings, with length k, over Σ.

  
• SOME CONVENTIONS

  • We shall use lower-case letters at the beginning of the alphabet to denote alphabet symbols (e.g., a, b)
  • Lower-case letters near the end of the alphabet to denote strings (e.g., w, x, y, z)
  • You should try to get used to this conventions, to help remind you of the types of the elements being discussed
• LANGUAGE

  -> A language L is a subset of Σ*: L⊆Σ*

  -AB denotes the concatenation of the language A and B.

  (AB={xy | x ∈ A, y ∈ B})
• PROBLEM

  -> In automata theory, a problem is the question of deciding whether a given string is a member of some particular language.

  It is common to describe a language using set constructor notation: