Results 1 to 4 of 4

Math Help - Help in Theory of Automata

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    2

    Help in Theory of Automata

    HI,
    I have an exam tomorrow. For which I've a sample paper(Unsolved) and another solved sample paper both of them have similar problems but not same. I can't solve the sample paper since I am new in Automata ... can anyone please help me ???

    Anyone who is master in Automata will not have any problem ... because i have a similar paper solved ..
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Sorry for a late response... Both papers have 10 questions each, but neither of them is about (finite) automata. So, which of the problem you would like help with, and why did you mention automata in your post?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    2
    Quote Originally Posted by emakarov View Post
    Sorry for a late response... Both papers have 10 questions each, but neither of them is about (finite) automata. So, which of the problem you would like help with, and why did you mention automata in your post?
    I studied this topic "Turing Machine" in a course named "Theory Of Automata" that's why i thought to ask about it on this forum .. as i said i am just a beginner in Automata .. please tell me is it the right forum to post such Questions like "Turing Machine problem" and all others that my Documents have .. ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Yes, this is the right forum. However, people are likely to provide help under certain conditions.

    1. You need to know basic definitions, theorems and methods of this topic. This includes the definition and examples of Turing machines (TM), decidable (recursive) and semidecidable (recursively enumerable) languages, reducibility as a way of showing undecidability or non-semidecidability, undecidability of Halting and similar problems, decidability of semi-decidable languages whose complement is also semi-decidable. Most likely, you also need Rice's theorem and possibly its generalization, Rice-Myhill-Shapiro theorem.

    If you are having difficulties with one of these topics, you may also ask questions about them, but these questions should be separate from questions about other problems, like those in the documents you provided. I mean that we can help with a separate question about a concept or theorem, and we can help with a problem that relies on this concept or theorem. But it may not be a good idea to ask help with a problem and expect that along with the solution, all background concepts will be explained as well.

    2. It may not be a good idea to expect the get solutions for 10 problems, some with as many as four subproblems. This place is more for hints than for comprehensive solutions to one problem, let alone the whole final.

    3. As with any topic here, it is good to show how you tried to solve a problem and what difficulties you are having, instead of quoting bare problem statement.

    To sum up, you can't rely on this forum only to bring you quickly up to speed in computation theory. You have to do a lot of studying from lectures and/or textbooks your course used, and post here occasional difficulties you encounter.

    Here are some ideas about problem #3 from the first document (without solutions).

    Prove that there is no Turing Machine that accepts the language L3 = {<M> | M does not accept any string it runs for more than 10 steps on}.
    For any TM M, let L(M)={w | M accepts w}. M diverges on words not in L(M). For a language L, L=L(M) for some M iff L is semi-decidable iff L is recursively enumerable.

    We can reduce the problem of accepting the language L0={<M> | L(M) is empty} to accepting L3. Since L0 is not semi-decidable, neither is L3.

    Suppose M is given. Then build M' such that M' does > 10 superfluous steps (like moving from one cell to the next and back) and then calls M. So, M' runs > 10 steps on every input. Then L(M) is empty iff L(M') is empty. Thus, <M> is in L0 iff <M'> is in L3, and we reduced the problem of membership in L0 to that of membership in L3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata Languages and DFA etc.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2011, 08:32 AM
  2. Automata
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: July 6th 2010, 07:20 AM
  3. Regular Expression (Theory of Automata)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2010, 04:58 AM
  4. Automata Proof... Theory of Computation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2008, 11:25 PM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum