Automata Theory and Formal Language

1. Automata

1.5 The Central Concept of Automata Theory

1.5.1 Alphabet

  • Alphabet is the finite, non-empty Set of the symbol
  • Using the \sum symbol stand for the Alphabet

1.5.2 String

String, sometime called word is a finite sequence of symbols, which choose from the Alphabet.

  • Empty String

If the string has no symbol, it is empty String, use the ϵ\epsilon stand for it.

  • String’s lenth

The number of symbol in the the string called the lenth of the string, use the w|w| stand for the lenth of string ww

  • The power of Alphabet

Use the exponent of the Alphabet like k\sum^k stand for the Set of string, which lenth is kk, in \sum
Notice that 0={ϵ}\sum^0 = \{\epsilon\}

The set of all strings in an Alphabet, use \sum^*
If remove the ϵ\epsilon in the normal Alphabet, the rest is called +\sum^+
\sum^+ = \sum^0\bigcup\sum^1\bigcup\sum^2\bigcup\dots

=+{ϵ}\sum^*=\sum^+\bigcup\{\epsilon\}

1.5.3 Language