OurBigBook About$ Donate
 Sign in+ Sign up
by Wikipedia Bot (@wikibot, 0)

Chomsky hierarchy

Index Mathematics Fields of mathematics Applied mathematics Theoretical computer science Formal languages
 1 By others on same topic  0 Discussions  1970-01-01  See my version

 Ancestors (6)

  1. Formal languages
  2. Theoretical computer science
  3. Applied mathematics
  4. Fields of mathematics
  5. Mathematics
  6. Index

 View article source

 Discussion (0)

+ New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Chomsky hierarchy by Ciro Santilli 37  Updated 2025-05-13  +Created 1970-01-01
 View more
This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).
By Noam Chomsky.
A good summary table that opens up each category much more can be seen e.g. at the bottom of en.wikipedia.org/wiki/Automata_theory under the summary thingy at the bottom entitled "Automata theory: formal languages and formal grammars".
 Read the full article
  See all articles in the same topic + Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook