下载文档原格式
形式语言与自动机的发展和在计算理论中的作用2015060104020王桢形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。
在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。
可是这项工作并没有所成果，对自然语言的结构理解太片面化，翻译质量不理想也很难提高。
1956年，乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。
他对语言进行定义：给定一组符号，称为字母表，用∑表示。
又用∑*表示∑中字母组成的所有符号串的集合。
∑*的每个子集都是∑上的一个语言。
乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。
同时克林在研究神经细跑中，建立了识别语言的系统有穷状态自动机。
乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用O 型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。
这一成果将形式语言引入数学，使得形式语言真正诞生。
1960年，算法语言ALGOL60报告发表。
1961年，又发表了ALGOL60修改报告。
在这两个报告中，第一次使用一种称为BNF范式的形式方法来描述程序设计语言ALGOL60的语法。
不久，人们即发现BNF范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。
形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。
在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。
形式语言与自动机的概念与应用形式语言与自动机是计算机科学中的两个重要概念，它们在计算机科学的理论研究和实际应用中扮演着重要的角色。
本文将介绍形式语言与自动机的概念，并探讨它们在计算机科学中的应用。
一、形式语言的概念形式语言是一个数学模型，用于描述符号集合和这些符号形成的规则。
在计算机科学中，形式语言被广泛应用于编程语言的设计和分析、自然语言处理等领域。
形式语言具有以下特点：1. 词汇表：形式语言由一个有限的字符集合构成，称为词汇表。
词汇表中的每个字符称为终结符号。
2. 语法规则：形式语言中的规则定义了如何使用词汇表中的字符构造合法的语句。
这些规则可以用产生式（production）表示，产生式由非终结符号和终结符号组成。
3. 句子：符合语法规则的字符序列称为句子。
一个形式语言可以包含无限个句子。
在形式语言的研究中，常常使用巴科斯范式（Backus-Naur Form，BNF）来描述语法规则。
二、自动机的概念自动机是从输入中接收一个字符序列，并据此转移到下一个状态的抽象计算模型。
它可以用于描述和处理形式语言。
在自动机理论中，常见的自动机包括有限自动机（Finite Automaton，FA）、下推自动机（Pushdown Automaton，PDA）和图灵机（Turing Machine，TM）等。
1. 有限自动机：有限自动机是一种能接受有限长输入，并根据事先定义的状态转移规则改变自身状态的计算模型。
它适用于描述正则语言，如正则表达式。
有限自动机包括确定性有限自动机（Deterministic Finite Automaton，DFA）和非确定性有限自动机（Nondeterministic Finite Automaton，NFA）。
2. 下推自动机：下推自动机是一种比有限自动机更强大的计算模型，它使用栈来存储和处理输入的字符序列。
下推自动机适用于描述上下文无关语言，如上下文无关文法。
下推自动机可以记忆无限长的输入。
形式语言与自动机的关系形式语言与自动机的关系形式语言与自动机的关系研究新疆师范大学数理信息学院数学03-6班形式语言的直观意义，自动机的直观意义，形式语言的定义，形式语言的特征，语法的分类，自动机的定义，自动机的分类，各种自动机的定义，形式语言和自动的的关系，自动机的对语言的例子形式语言的定义；自动机的定义；形式语言和自动机的关系1，形式语言的直观意义直观地讲，形式语言是用来精确描述语言和它结构的手段。
它一重写规则α→β的α, β均为字符串。
形式来表示，其中，重写规则就是在包含α的字符穿中遇见规则左边的α时，α部分重新写为右边的β。
这样一个初设的字符串通过不断地运用重写规则，就可以到另一个字符串。
通过选择不同的规则并且以各种不同的顺序来运用最这些规定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。
2，形式语言的定义形式语法是一个四元组G=（N, V, P, S）, 其中N 是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。
V 是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中具体的词，终端语符集这种语言的词库，P 是以重写规则的有限集合，基本形式P {α→β}，即" α改写为β" ，其中箭头表示指令，一条规则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或语符序列之间的关系，而S 是一个特定的初始符；3，语法的分类乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则语法，上下文有关语法，上下文无关语法；有这些语法生成的语言是正则语言，，上下文有关语言，上下文无关语言，递归数集合。
a 如果P 中的规则，满足如下的形式：A →Bx 或，A →x ，其中，A,B 是非终结符，x 是终结符，则G 称为正则语法（简称为FSG ）。
b 如果P 中的规则，满足如下的形式：A →α, 其中，A 是非终结符, α是由N 和V 中字符所组成的字符串（或可表示为α∈(N V )*, *意味着它右边的字符可以重复0到任何多次），则G 称为上下文无关语法（简称为CFG ）。
