# Thread: Help in Theory of Automata

1. ## 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 ..

2. 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?

3. Originally Posted by emakarov
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 .. ?

4. 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.