1.1 finite automata

finite automata = finite state machine

computational model: idealized computer

e.x. 自动门

需要1bit来存储state - state: 开启/关闭 - condition: 前面有人后面没人、前面没人后面没人……

e.x. Markov chains

patterns of data

Formal Def of a Finite Automation

A finite automation is a 5-tuple(),where:

  • Q is a finite set called the states
  • is a finite set called the alphabet
  • is the transition function
  • is the start state
  • is the set of accept states

language of machine M: L(M)=A

If , then M recognizes A

Formal Def of Computation

Let M=() be a finite automation and be a string over alphabet . Then M accepts w if a sequence of states exists in Q with the following three conditions:

  • , for

A language is called a regular language if some finite automation recognizes it.

Designing Finite Automata

收集作出决策(每读入一个字母时)所必要的最精简信息,然后决定用几个状态来储存这些信息,并寻找他们之间的逻辑,最后确定start state和set of accept states。

另外还可以分类讨论每一个input

The Regular Operations

i.e. the properties of finite automata & regular languages Let A and B be languages. Define regular operations as follows:

  • Union:
  • Concatenation:
  • Star:

The class of regular languages is closed under these operation. (It will be easier for us to prove after learning nondeterminism.)