第1个回答 2009-11-04
他还活着，我看过他的纪录片。。。
我们上课也讲过，不过是英文的哦， 你的分比较少，我就不帮你翻译了哦，你英文好的话看得懂的吧：
四点：
1：arbitrary grammars can describe any language;
2：by requiring the left hand side of rules to contain at most one nonterminal, we get context-sensitive grammars;
3：by requiring left hand sides to consist of a single nonterminal, we get context-free grammars;
4：by requiring all right hand sides to consist of a terminal followed by a nonterminal, we get the (left) regular grammars;
these four categories of grammars describe the four categories of languages of the Chomsky hierarchy.
关于对计算机的意义和作用：
The Chomsky hierarchy is a hierarchy of classes of formal languages. Regular languages are the smallest set; context-free languages are a superset of these; context-sensitive are a superset of those; computable languages are again a superset.
They can be characterised by different types of devices used to recognise these languages: finite state automata , pushdown automata, linear bounded automata, and Turing machines, respectively.