1
$\begingroup$

I saw the book suggested here.

Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?

I ask since, looking through a pdf copy of the book, I found no matches with "Chomsky Hierarchy", but perhaps it is covered with a different name.

Improve this question
$\endgroup$
1
  • $\begingroup$ I reviewed every page of that textbook basically before I wrote my answer. Is it convincing enough? $\endgroup$
    – John L.
    Commented May 9, 2023 at 17:12

1 Answer 1

Reset to default
1
$\begingroup$

No, Sipser's textbook does not cover Chomsky hierarchy, a containment hierarchy of different classes of formal grammars. Nor does it cover that hierarchy with a different name. In fact, the book does not mention any formal grammar other than context-free grammar.

That textbook does cover many related concepts such as regular language and finite state automaton, context-free grammar and context-free language and non-deterministic pushdown automaton, linear-bounded deterministic Turing machine, recursively enumerable and Turing machine. It certainly covers context-free grammar pretty well. It is not surprising the post linked in the question recommends it for understanding formal grammars.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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