CS402 GDB Fall 2020 Solution

 Graded Discussion Board

For formal languages, Noam Chomsky identified formal grammars into four categories known as Chomsky Hierarchy. For each grammar, there is an automaton accepting it.

A mathematicians group at Hopkins University, California needs a machine to implement a language L derived after some calculations where L={aⁿ bⁿ cⁿ dⁿ , n≥1}. They have limited memory resources for the implementation.

Discuss which machine among FA (Finite Automata), PDA (Push Down Automata), LBA (Linear Bounded Automata) and TM (Turing Machine) is the most favourable one for the scenario by keeping in view the above language as a function of ‘n’ and limited memory resources. Give proper reasoning.

Solution

Turning machine is the most favorable one for the scenario by keeping in view the above language as a function of ‘n•’ and limited memory resources.

Turning Machine (TM)

For solving any recursively enumerable problem. For the implementation of neural networks.

For the implementation of Robotics Applications. For the implementation of artificial