New NABARD Workshop - Last 4 year trend. March 5 at 5 PM. Register here

    Question

    What is the minimum number of states required in a

    Turing Machine to recognize the language L = { aⁿbⁿ | n ≥ 1 }?
    A 2 Correct Answer Incorrect Answer
    B 3 Correct Answer Incorrect Answer
    C 4 Correct Answer Incorrect Answer
    D 5 Correct Answer Incorrect Answer

    Solution

    A Turing Machine (TM) for L = { aⁿbⁿ | n ≥ 1 } needs at least four states: 1. Initial state to scan ‘a’ 2. Intermediate state to replace ‘a’ and find ‘b’ 3. State to match ‘b’ with ‘a’ 4. Final accepting state

    Practice Next

    Relevant for Exams: