Automata Theory and Formal Language

Wafer Li ... 2016-10-14 复习
  • 复习
  • 自动机
小于 1 分钟

# 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^+ +=012\sum^+ = \sum^0\bigcup\sum^1\bigcup\sum^2\bigcup\dots


# 1.5.3 Language