Loops & Formal Languages
Using the loop based taxonomy of digital systems results:
Then there is the following morphism between the loop based
taxonomy of digital machines and the Chomsky's taxonomy of formal
- finite automata belong to 2OS, two-loop machines (one for memorizing the state and another for computing the next state)
- stack automata belong to 3OS, three-loop machines (an additional loop to use a simple memory: LIFO memory)
- linearly bounded memory automata belong to 4OS, four-loop machines (the forurth loop to improve the memory function)
If the "expressiveness" of formal languages increases (from type 3
to type 1), then the autonomy of the machines used to recognize or to
generate them increases accordingly (from 2-loop machines to 4-loop
- type 3, regular languages &harr 2OS,
- type 2, context free languages &harr 3OS,
- type 1, context dependent languages &harr 4OS.
[Stefan '91] Gh. Stefan,: Functie si structura in sistemele
digitale (Function and Structure in Digital Systems), Ed. Academiei
Romane, Bucuresti, 1991.
[Stefan '97] Gh. Stefan: Circuit Complexity, Recursion, Grammars and Information.
Multiple Morphisms, Ed. Transilvania University of Brasov, 1997.
[Stefan work in endless progress] Gh. Stefan:
Loops & Complexity in Digital Systems. Lecture Notes on Digital Design in the Giga-Gate/Chip Era
[Stefan '07] Gheorghe Stefan: "Chomsky's Hierarchy & a Loop_Based Taxonomy for Digital Systems", in Romanian Journal of Information Science and Technology vol. 10, no. 2, 2007.