In Hopcroft-Motwani-Ullman there are exercises on this topic. What is another good reference (textbook/website) for fractional/quotient regular languages, possibly with examples?

  • $\begingroup$ I've never heard of "Fractional languages" -- what are they? $\endgroup$
    – Ben I.
    Dec 18 '20 at 3:38

An Introduction to formal Languages and Automata

Included in the University of Nottingham's Languages and Computation Course resources

The book An Introduction to Formal Languages and Automata by Peter Linz can be used as an alternative or complement to Hopcroft-Motwani-Ullman.

An excerpt from

The latest edition of Linz’s theory textbook follows the same outline as the previous one: it begins with a chapter on mathematical preliminaries; moves through the Chomsky hierarchy (regular, context-free, and recursively enumerable languages, with a brief mention of context-sensitive languages); and concludes with one chapter each on the topics of undecidability, alternate models of computation, and complexity classes.

The presentation suits your needs : gives formal definitions, provide examples, give mathematical justifications (usually complete proofs), and end with a set of exercises. Solutions to some of the exercises appear in the appendix.

More than anything else, the book needs to provide readers with a broader framework that naturally motivates the many topics covered. Instructors looking for a general reference on automata and formal languages, or a textbook for a mathematically sophisticated audience, should take note that Linz’s book lacks a comprehensive bibliography (the one-page list of references consists primarily of other theory textbooks).

Overall, the work is appropriate for the author’s stated purpose: a textbook for an introductory undergraduate course on the theory of computation—provided that the students have sufficient mathematical preparation.


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.