Question

Consider the following automata in increasing processing power :
A. Linear bounded automata
B. Turing machine
C. Finite automata
D. Pushdown automata
Choose the correct answer from the options given below :

• A. A, B, D, C
• B. C, D, A, B
• C. B, A, C, D
• D. C, D, B, A

Hint:

Remember the acronym FP-LT for the Chomsky Hierarchy machines: Finite, Pushdown, Linear-Bounded, Turing. Power increases as you go from F to T!

Answer 1

The Correct Option is B

Concept:
• The Chomsky hierarchy classifies grammars and their corresponding automata based on their generative and computational power.
• Computational power refers to the complexity of languages the machine can recognize and the flexibility of its memory/storage.
• The hierarchy from least powerful to most powerful is: Regular $\subset$ Context-Free $\subset$ Context-Sensitive $\subset$ Recursively Enumerable.

Step 1: Identify the power of Finite Automata (C)
Finite Automata have the least processing power as they have no external memory (only states). They recognize only Regular Languages.

Step 2: Identify the power of Pushdown Automata (D)
Pushdown Automata are more powerful than FA because they have an infinite stack for memory. They recognize Context-Free Languages.

Step 3: Identify the power of Linear Bounded Automata (A)
LBAs are more powerful than PDAs as they can use the input tape itself for restricted read/write operations. They recognize Context-Sensitive Languages.

Step 4: Identify the power of Turing Machines (B)
Turing Machines have the highest processing power as they have an infinite read/write tape. They can simulate any algorithmic process and recognize Recursively Enumerable Languages.

Step 5: Arrange in increasing order
The order of increasing power is C (Finite) $\rightarrow$ D (Pushdown) $\rightarrow$ A (Linear Bounded) $\rightarrow$ B (Turing Machine).