计算语言学：形式语言与自动机——乔姆斯基理论

"计算语言学PPT 乔姆斯基 自动机 形式化语言" 这篇资料主要探讨了计算语言学的基础概念，特别是在形式语言与自动机的框架下，结合了乔姆斯基的理论。计算语言学是一门研究如何用计算机处理自然语言的学科，它涉及到计算机科学、语言学和统计学等多个领域。 首先，课程提到了语言的两种定义方法。第一种是代数学的定义，即确定性定义，它认为语言是句子的集合。在这里，句子是指符合特定规则的符号序列。第二种是统计学的定义，也就是不确定性定义，它将语言视为一个概率分布，每个句子都有对应的出现概率，这在处理大量自然语言数据时非常有用。 接着，文档讨论了描述语言的不同方式。枚举法虽然直观但不适合描述包含无限多句子的语言。因此，更常用的方法是通过语法和自动机来描述。语法提供了一种生成语言中所有句子的机制，而自动机则给出了识别这些语言中句子的机械过程。 在形式语法的阐述中，提到了四个关键组成部分：终结符（VT）、非终结符（VN）、起始符（S）和重写规则（P）。终结符是构成句子的实际符号，相当于单词或字母表；非终结符则在推导过程中起到变量的作用，代表语法结构的一部分。起始符S是语法推导的起点，通常代表句子。重写规则定义了如何通过替代来构建或变换符号串。 形式语法的表示通常是一个四元组G=<VT, VN, S, P>，其中P包含了产生式规则。这些规则定义了如何从非终结符转换为终结符或非终结符，从而构造出合法的句子。推导过程描述了如何从起始符S通过应用规则得到最终的句子，生成的语言L(G)由所有可能的推导结果组成。 最后，文档提到了乔姆斯基的语法层级，包括0型语法（无限制语法）、1型语法（上下文相关语法）、2型语法（上下文无关语法）和3型语法（正规语法）。这个层次结构对语言的复杂性进行了分类，不同的类型对应于不同复杂度的自动机可以识别的语言。 这份PPT深入浅出地介绍了计算语言学的基础，特别是形式语言的描述方法和乔姆斯基的语法理论，这些都是理解和设计自然语言处理系统的关键概念。