# 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.