Loops & Formal Languages
Using the loop based taxonomy of digital systems results:
- 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)
Then there is the following morphism between the loop based
taxonomy of digital machines and the Chomsky's taxonomy of formal
languages:
- type 3, regular languages &harr 2OS,
- type 2, context free languages &harr 3OS,
- type 1, context dependent languages &harr 4OS.
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
machines).
References
[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.