Atitit 四种自动机 fsm pda

Atitit 四种自动机 fsm pda

目录

1. 自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。 2

1.1. 抽象自动机的理论。 2

1.2. 自动机就是语言的解释器 ati总结 2

1.3. 四种形式语言四种文法对应四种自动机 2

2. 四种自动机 fsm pda lba turin 2

2.1. FSM "finite state machine"有限状态自动机(FSM "finite state machine  正则语言机器 2

2.2. 图灵机模型（无限状态的自动机）;用来描述通用计算机计算能力的图灵机模型; 2

2.3. PDA下推自动机;push down automata 3

2.4. LBA线性有界自动机 (linear bounded automaton)上下文有关语言的识别接受器。 3

3. 对语言的识别能力上讲： 有限状态自动机<非确定下推自动机<线性有界非确定图灵机<图灵机（无限状态的自动机） 3

4. 其他类型自动机 3

5. 四大文法 4

5.1. 0型文法（对应图灵机）也称短语文法，记为PSG。 4

5.2. 1型文法（对应线性界线自动机，自然语言）上下文有关文法，记为CSG。 4

5.3. 2型文法（对应下推自动机，程序设计语言）上下文无关文法，记为CFG。 4

5.4. 3型文法（对应有限自动机）也叫正规文法，记为RG。 4

6. ref 5

1. 自动机可分为有限自动机、后进先出自动机、线性有界自动机、图灵机等几种。它们对语言的识别能力各不相同。1.1. 抽象自动机的理论。

抽象自动机是一种能够识别语言的抽象的装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统，这样的抽象自动机可以用来检验输入的符号串是不是语言中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收它。如图所示:

1.2. 自动机就是语言的解释器 ati总结1.3. 四种形式语言四种文法对应四种自动机2. 四种自动机 fsm pda lba turin

2.1. FSM "finite state machine"有限状态自动机(FSM "finite state machine  正则语言机器

计算能力

确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机(下推自动机或图灵机)不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的算法。

2.2. 图灵机模型（无限状态的自动机）;用来描述通用计算机计算能力的图灵机模型;

图灵机（无限状态的自动机）

2.3. PDA下推自动机;push down automata

2.4. LBA线性有界自动机 (linear bounded automaton)上下文有关语言的识别接受器。

一种图灵机.是把计算限制在仅仅包含输人的那一段带上的图灵机.可用作上下文有关语言的识别接受器。

线性有界自动机(缩写为LBA)可形式地由M=<K,}',1',8,qo,F)来表示.其中:K是状态的有限集;尸是带符号的有限集;}}1'是输人符号集;K中的q。是起始状态;FcK是终结状态集;8是从KXI'到KXI'X {L,R}子集的映射，<L,R)分别是读写头左右移一格.刃含有两个特殊的符号，通常记为本和$，它们分别是左端标志和右端标志.这些符号开始就处在输人带的端点，其作用是阻止带头离开带上出现符号的区.

3. 对语言的识别能力上讲：
有限状态自动机<非确定下推自动机<线性有界非确定图灵机<图灵机（无限状态的自动机）4. 其他类型自动机

由下推表组成的单项非确定程序的下推自动机;

线性有界自动机;

用来描述通用计算机计算能力的图灵机模型;

进行与转移函数，转移状态有关输出的时序机;

由一些基本语句构成程序框图的波斯特机;随即存储机;

堆栈自动机;

不受有限自动机做控制器和存储限制的无限自动机;

统计自动机某一条件概率分布的概率自动机和细胞自动机。

5. 四大文法

一般的文法至少都是0型文法，也就是说0型文法限制最少。若将0型文法比作基类的话，1、2、3型文法就是不断继承并加以限制得到的子类。
文法表示过程中，常用大写字母表示非终结符V_N，而小写字母表示的是终结符V_T。

5.1. 0型文法（对应图灵机）也称短语文法，记为PSG。

· 一个非常重要的理论结果是：0型文法的能力相当于图灵机。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。

5.2. 1型文法（对应线性界线自动机，自然语言）上下文有关文法，记为CSG。

· 此文法对应于线性有界自动机。

5.3. 2型文法（对应下推自动机，程序设计语言）上下文无关文法，记为CFG。

·  2型文法也叫上下文无关文法，记为CFG。

· 此文法对应于下推自动机。

5.4. 3型文法（对应有限自动机）也叫正规文法，记为RG。

· 它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。

· 3型文法也叫正规文法，记为RG。

· 此文法对应于有限状态自动机。