7 Automata
Various topics in theoretical computer science deal with the classification of formal languages with respect to their complexity, where different disciplines use different measures of “complexity.” Typically, a formal language is a subset of a finitely generated free monoid Σ∗. The word “formal” serves to distinguish these languages from natural languages. In many cases, we omit this adjective and call L ⊆ Σ∗ a language. The classification of languages can be done from rather different points of view. A well-known approach is the Chomsky hierarchy by Avram Noam Chomsky (born 1928), where grammars are used as description mechanisms. The class of regular languages coincides with Type-3 in Chomsky’s hierarchy. This class is particularly ...
Get Discrete Algebraic Methods now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
