practice_exam_2018

COSC 1105/1107 - Computing Theory Mock Exam | Page 2 of 2 (e) (8 marks) A decimal number consists of: (A) an optional + or — sign; (B) a string of digits; (C) a decimal point; and (D) another string of digits. Also, either the string of digits in (B) or (D) can be empty, but at least one of the two strings of digits must be nonempty. Finally, the decimal point appears if and only if the string of digits (D) is not empty. Draw the state diagram of an NFA which accepts decimal numbers. For example, the NFA should accept 132.424, 18888, and .87, but should reject 32.3.23, 187., and .98.1. You can use abbreviations such as 0-9 on transitions if you wish. Question 4: Pushdown AUtOIMAata . .. ... ...o.uuiiiiii 10 marks Consider the pushdown automaton M below (—X means popping X from the stack; +X means pushing X to the stack. The empty string is denoted ). o+ X, b+Y p—y a—X,—X FOEOSNO (a) (3 marks) Trace the execution of M with inputs aabcbcaa, aabcbea, and abcbcaaa. (b) (4 marks) Describe the language of /M in set notation and informally. (¢) (3 marks) How does the language of M change if we replace the transition from ¢ to gz with 0 (q1,¢€ €) = (g2,¢€) and we add the transition §(gs, €, €) = (g1, €) in M?. In one to three sentences, briefly explain your answer. Question 5: Turing Machines . ... ... ..... ooiiiiiii i e 16 marks Consider the Turing machine M = ({qo, 1, g2, 43},10, 1, B}, #, 0, qo, {qgs}) where transition ¢ is defined as: ) 0 1 + qo (Q2707R> (Q1717R) (Q?n#)L) q1 (Q2717R> (QO717R> <Q37#7L> q2 (QO707R) (Q1707R) (Q37#7L> d3 (a) (2 marks) Draw the Turing Machine M. (b) (4 marks) What is the outcome of the computation of M with the inputs 600001100104 (the state 1s written immediately to the left of the symbol being read)? Briefly explain your answer. There is no need to give traces. (¢c) (3 marks) Describe informally the result of a computation in M. (d) (7 marks) Provide a Turing machine M which given a string w over (0, 1)* behaves as follows: e If w contains an odd number of 1’s and an odd number of 0’s, then M converts w into the binary successor of w, i.e. M adds 1 to the binary number represented by w. e Otherwise, M converts all the 1’s to O’s. For example, given the strings 100101, 10011 and 11111, your machine should terminate with outputs 100110, 00000 and 00000 respectively. You may use any notation for Turing machines and any variety of Turing machine that you wish. Question 6: Languages and Computability .. ... 15 marks (a) (2 marks) What is a decision problem? What decision is made in the case of a 3SAT problem? (b) (4 marks) Explain what a Universal Turing machine U is and what U(U, (M, w)) would be equal to. (¢) (2 marks) Could there be an undecidable NP-complete problem? Justify your answer. (d) (7 marks) Prove that the problem of deciding any Turing Machine halts for some input is undecidable. End of mock exam paper