CSc 30400 Introduction to Theoretical Computer Science

Fall 2008

Instructions on the exam

1. NFAepsilon -> NFA
2. NFA -> DFA
3. DFA -> min DFA
4. reg. expr. -> NFA
5. DFA -> reg. expr.
6. A formal proof that the regular languages are closed under an operation
7. you will find out on Tuesday ... :-)

• Questions 6 and 7 should be relatively easy if you understand what's going on in this course. So, if you feel familiar with the material try them first (their answers should come immediately into your mind by the time you read the questions, if not skip them right away, don't lose time on them).
• The other questions are generally more time consuming, especially if you follow the methodology step by step. However if you don't want to risk, you should be prepared on the methodology for all the above conversions 1-5, so you should practice a lot in order to make sure that you will be able to do all of them in a reasonable amount of time and under the pressure of the exam (look again at the homework and the examples we did in class, try to solve them from scratch and compare your results with the answers that we gave, try to solve some more questions from your book etc...)
• It took me about 20 minutes to solve all the 7 questions on paper step-by-step (each question took 1-5 minutes), so I assume that 1 hour and 15 minutes should be more than enough time for just 5 of them. When (and if) you are done with the mandatory 5 feel free to do some more since I will either grade the best 5 or give extra credit to the extra questions (I haven't decided yet...)
• It is always good to have choices. However you might end up reading the questions again and again without deciding which 5 you should choose. An advise on that: First read just once all the questions. Then start with those that you feel more familiar with. You already know most of the questions so it shouldn't be difficult to come up with a decision. Furthermore I think that all the questions have pretty much the same difficulty so another suggestion would be just to pick 5 at random!!!
• The exam is open book and open notes (you are also allowed to have the solutions of the homework with you).  Make sure that you study and carry with you the ppt notes that I uploaded on the web page. It will be very handy to have them during the exam. However be careful! You shouldn't spend time on studying the methodology during the exam, else the time won't be enough for sure! Furthermore your notes should be carefully organized (you should know in advance what is contained in the notes that you are carrying with you and where exactly you can find it).

• In questions 1-5 you don't have to explain your answer. If you are 100% sure about the answer and you don't want to lose time on writing all the steps just give the answer and you will get full credit. However, I won't give partial credit for a wrong answer with no intermediate steps and no explanations.
• You can use scratch paper if you want but you should write the answers on the exam paper. I assume that I can get scratch paper from the department but since I am not sure yet you should bring some with you too.
• Creating discussion groups during the exam is not allowed! :-P