Entry
Compiler: Language: Overview: Hierarchy: Chomsky: Model: What is the Chomsky hierarchy?
Oct 25th, 2003 16:04
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 24 October 2003 - 10:23 pm --------------------
Compiler: Language: Overview: Hierarchy: Chomsky: Model: What is the
Chomsky hierarchy?
---
The Chomsky hierarchy is named after the American linguist and
philosopher of language Noam Chomsky.
---
Although hundreds of computing models have been proposed since the
the inception of computer science, each has tended to be
equivalent to just one of four principal models:
1. finite automata
2. pushdown automata
3. linear bounded automata
4. Turing machines
---
Since each model is more general than its predecessor
in the hierarchy, each model includes the one before it.
---
Each model of computation determines a class of languages.
---
Since each class of languages is more general than its predecessor
in the hierarchy, each class of languages includes the one before it:
---
Ordered from less general to more general:
---
1. computing model = finite automata
language class = regular languages
---
2. computing model = push down automata
language class = context free languages
---
3. computing model = linear bounded automata
language class = context sensitive languages
---
4. computing model = Turing machines
language class = recursively enumerable languages
---
[book: source: Dewdney, Alexander Keewatin - the Turing omnibus, 61
excursions in computer science - p. 43 - 'The Chomsky hierarchy' -
http://www.amazon.com/exec/obidos/tg/detail/-
/0805071660/qid=1066986136/sr=1-4/ref=sr_1_4/103-7895116-2553433?
v=glance&s=books]
---
---
Internet: see also:
---
Compiler: Syntax: Parsing: Grammar: What is a grammar?
http://www.faqts.com/knowledge_base/view.phtml/aid/25946/fid/1263
---
Compiler: Grammar: Expression: Regular: Which grammar defines set of
all regular expressions? [BNF]
http://www.faqts.com/knowledge_base/view.phtml/aid/25950/fid/1263
---
Compiler: Syntax: Parser: LL versus LR: What is the difference between
an LL and an LR parser?
http://www.faqts.com/knowledge_base/view.phtml/aid/25934/fid/1262
---
Compiler: Syntax: Parser: Animation: Where to find animation tools for
parsing?
http://www.faqts.com/knowledge_base/view.phtml/aid/25932/fid/1262
----------------------------------------------------------------------
