G. STEFAN
Chomsky's Hierarchy & A Loop-Based Taxonomy for Digital Systems

Abstract.
Formal languages are supported by digital systems having a correspondent hierarchy. We show that Chomsky's taxonomy is paralleled by a loop-based hierarchy for digital systems. The machines used to recognize or generate a type n formal language belong to a specific class, differentiated from the one used for a type (n–1) language (for n = 1, 2, 3). The difference between classes is given by an additional hardware loop closed in the last. Each new loop increases the autonomy of the system, making it able to support a more “expressive” language with a less restrictive grammar. We prove the correspondence between type 3 languages and 2-loop machines, between type 2 languages and 3-loop machines, and between type 1 languages and 4-loop machines.

READ THE PDF