Han*_*Sun 4 compiler-construction math computer-science
在维基百科https://www.wikiwand.com/en/Formal_language上,我找到了正式语言的定义:
在数学,计算机科学和语言学中,形式语言是一组符号串,可能受到特定于它的规则的约束.
这看起来很抽象.我无法想象任何不符合这个定义的语言.有没有人对非正式语言看起来是什么以及它如何不符合定义？
让我先谈谈你的问题.一个很好的非正式语言的例子是自然语言.英语和斯洛文尼亚就是例子.Tagalog和Tarifit Berber也是如此.不幸的是,语言学家似乎没有对所有人都同意的自然语言的定义.
诺姆·乔姆斯基(Noam Chomsky)在其1956年的论文"语言描述三种模型"(Three Models for the Language of Language)中尝试使用无背景伽玛来模拟自然语言.他在那篇论文中发明了(或发现,如果你愿意的话); 虽然他并没有这样称呼他们; 虽然它们对英语语言模型没有用,但它们彻底改变了计算机科学.
形式上,形式语言只是有限字母表中的一组字符串.而已.
示例包括所有有效的C程序,所有有效的HTML文件,所有有效的XML文件,所有"平衡"括号的字符串(例如(), ()(), ((()))()(()), ...),始终停止的所有确定性图灵机的集合(某些编码下的代码),所有简单的集合可以使用k-colors(实际上是某些编码下的代码)着色的图形,以a结尾并以a开头的所有二进制字符串的集合1等.
有些使用正则表达式(或者等效地,DFA)很容易识别; 有些是不可能使用DFA识别的,但可以使用PDA识别(或者,等效地,可以用无上下文语法描述); 其他人不承认这样的描述,但可以通过图灵机识别; 有些甚至不是图灵机(称为不可计算机)也无法识别.
这就是定义如此有用的原因.我们在CS evey日遇到的许多事情都可以用正式语言来表达.
为了对这个主题做一个很好的介绍,我强烈推荐Hopcroft等人出版的"自动机理论,语言和计算简介 ".