0
$\begingroup$

I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably context-free grammars and regular grammars), but not one that specifically deals with formal grammars as an object.

Is there a good textbook for this?

$\endgroup$
5
$\begingroup$

Probably the most-used textbook today is:

  • Hopcroft, Motwani, & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition).

A couple of other common ones are:

  • Sipser, Introduction to the Theory of Computation.
  • Linz, An Introduction to Formal Languages and Automata.

And a couple of older ones:

  • Michael Harrison, Introduction to Formal Language Theory. Many learned from this 1978 classic. Even though it's older, it has the advantage that you can pick up a very inexpensive used copy from online retailers.
  • Thomas Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science. It's up to the 3rd edition now, but the first edition was my textbook when I was an undergraduate. The exercises are excellent, but it's light on examples.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.