Skip to content

关于本章

本章节，首先描述上面是"formal"，引出Formal language， 然后对它进行详细的分析。维基百科的Formal language内容是非常好的（全面，深入浅出），需要仔细阅读。

首先说明formal language，formal grammar，automata，Chomsky hierarchy等基本概念，建立理论框架。

然后按照Chomsky hierarchy的每一层进行说明，对Chomsky hierarchy的每一层的说明采用如下顺序，即：

这是因为从Type-3 grammars到Type-0 grammars，grammar越来越抽象，越来越难理解，这样由易到难会比较符合认知规律。

在了解了这些之后，我们不能够仅仅局限于此，而是应该走向更加宽广的理论：Theory of computation，因为按照2012 ACM Computing Classification System，前面所讨论的formal language，automata theory都属于此范轴。

理论往往不是孤立的，而是相互关联，相互借用的，相互启发的，在阅读Formal language时，你会发现作者对它进行了大量的发散，涉及到的学科有mathematics（尤其是 Mathematical logic）, computer science, and linguistics。所以，在阅读的时候，就有必要梳理清楚概念之间的关系，抓住问题的本质，而不是被表面的描述识所扰乱。

学习计划--从入门到精通

Formal language所涉及的理论较多，并且大多数都是比较抽象的，刚开始学习（尤其对于缺乏使用programming language的人来说）可能会感觉比较吃力，以下是觉得比较好的学习计划：

首先搞清楚what is language、what is formal language、what is formal grammar、what is automata、What is the relationship between them，这样就建立起了建立起高屋建瓴的视野，这其实就是算入门了。推荐阅读下面的文章：

入门了之后，就需要建立起theory framework，最终我们会发现，使用Chomsky hierarchy就能够将整个理论给统一起来；然后再逐个进行细致分析，最后就能够融会贯通，这其实就是精通了。

Formal language

提及formal language，就得请出Noam Chomsky，因为下面的理论框架是由他所建立的，该theory framework的是按照Chomsky hierarchy来进行组织的：

Chomsky hierarchy Grammars Languages Abstract machines
Type-0 Unrestricted Recursively enumerable Turing machine
— (no common name) Decidable Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
— Positive range concatenation Positive range concatenation* PTIME Turing Machine
— Indexed Indexed* Nested stack
— — — Thread automaton
— Linear context-free rewriting systems Linear context-free rewriting language restricted Tree stack automaton
— Tree-adjoining Tree-adjoining Embedded pushdown
Type-2 Context-free Context-free Nondeterministic pushdown
— Deterministic context-free Deterministic context-free Deterministic pushdown
— Visibly pushdown Visibly pushdown Visibly pushdown
Type-3 Regular Regular Finite
— — Star-free Counter-free (with aperiodic finite monoid)
— Non-recursive Finite Acyclic finite

Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

Expressive power

Type-3->Type-2->Type-1->Type-0

Linear structure->hierarchy structure->graph->...

relation越来越复杂，structure越来越复杂；

Expressive power逐渐增强；

入门读物

入门读物推荐：

除此之外，推荐阅读如下巨著：

Cinderella Book VS Dragon Book

Introduction to Automata and Language Theory(aka Cinderella Book)是该领域的经典书籍。

Introduction to Automata and Language Theory(aka Cinderella Book)和Compilers: Principles, Techniques, and Tools (aka "Dragon Book")中的内容其实是紧密关联的，这不仅仅是因为Jeffrey D.Ullman参与了这两本书的编写，而是因为programming language是一种formal language，而Cinderella Book和Dragon Book其实都是在讲述和formal language相关的内容，当然，这些内容仅仅书中的一部分。Cinderella Book专注于讲述automata and language theory，而dragon book的内容则可以分为两个部分front end和back end，显然front end所讲述的内容就和automata and language theory紧密相关了。

参考

本项目的内容大多数来自: