Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Toc Assignment No-05 2024

    Uploaded by

    shreeyashwadhe

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Toc Assignment No-05 2024

    Uploaded by

    shreeyashwadhe
    8 views2 pages

    Original Title

    TOC ASSIGNMENT NO-05 2024

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    8 views2 pages

    Toc Assignment No-05 2024

    Uploaded by

    shreeyashwadhe

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Theory of Computation TE(2019) Computer Engineering

    MET’S Institute of Engineering, Nashik.


    THEORY OF COMPUTATION
    DEPARTMENT OF COMPUTER ENGINEERING
    Subject : TOC ASSIGNMENT NO – 05 Unit : V

    THEORY QUESTION (atleast Solve Any 5)

    1. Explain Language acceptance by TM.


    2. Explain the representation of TM.
    3. Differentiate between FA and TM.
    4. Define TM. And Explain recursively enumerable set.
    5. Explain the power of Turing Machine over Finite Automata.
    6. Write a short note on Halting Problem of Turing Machine.
    7. Write short notes on 1) Non-deterministic TM
    2) Composite TM
    3) Halting problem of TM.
    4) Limitation of TM
    8. Write a short notes on 1) Universal TM 2) Multi tape Turing Machine
    9. Write a short notes on 1) Unsolvable problem 2) Application Turing Machine
    10. What is Turing Machine. Give the formal definition of TM. Design a TM that
    replaces every occurrences of abb by baa
    11. How can Turing Machine compare with computer.

    TURING MACHINE PROBLEM(atleast solve any 10)


    n n
    12. Obtain TM to accept language L = { 0 1 | n  =1 }

    13.Design TM for the language L={02n} over 0,1


    14. Construct TM for – L = { All string with equal nos of a’s and b’s.}

    15. Construct a TM to compute L  {an b2n | n >0} Write simulation for the string.
    i) abb ii) aabbbb
    n n
    16. Construct a Turing Machine for the language L = {a b c | n>=l}
    n n n
    17. Construct a Turing Machine for the language L = {0 1 0 | n>=l}

    SPPU University asked questions from 2015-2019 Prepared By : Mr. Anand Gharu
    Theory of Computation TE(2019) Computer Engineering

    18. Design TM to accept the set L of all strings formed with 0 & 1 and
    having substring ‘000’
    19. Design a Turing machine for well formed parenthesis
    20.Construct a Turing Machine to accept the language
    n n n
    L = { a b a | n>=1 }

    21.Construct a Turing Machine which accepts odd length palindrome over


    the Σ={a,b}
    22. Design TM to recognize an arbitrary string divisible by 4 for  = {0, 1, 2}
    23. Construct a Turing Machine to accept string with equal nos of 0’s and 1’s.
    24. Construct TM for 1’s complement of binary number.
    25. Construct TM for 2’s complement of binary number.
    26. Design a TM to accept language
    L = { w / w (0 + 1)* } containing the substring 001.

    27. Construct a TM to accept language of even nos of 0’s and 1’s.

    28. Design TM to add unary number .


    29. Design a TM that multiplies two unary numbers over  1.
    Write simulation for the string 11 & 111

    RE TO TURNING MACHINE(solve all)

    30.Construct a Turing Machine R = (aba*b)


    31.Construct a Turing Machine R = (a + b)* bb
    32.Construct a Turing Machine L = a* ba* b

    ****************** Best of Luck *******************

    SPPU University asked questions from 2015-2019 Prepared By : Mr. Anand Gharu

    You might also like