CSI 301 Exam 1 With Solution, Fall 2012

AMERICAN UNIVERSITY OF SCIENCE AND T ECHNOLOGY COMPUTER SCIENCE REPARTMENT A1/11/2012 EXAMI y f / COURSE: CSI 301 THEORY OF COMPUTATION, / INST: MR. ELIE NASR oe wea SEMESTER: FALL 2012-2013 4 | ( Ay rs | ae a Question #1-(10 points) \ \ ad Consider the DFA with the following transition gable: (15 points) / : : 0 | E 42 1 [>A a epee es _ B _ (es Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct. A is the initial state and B is the final state ao mente ) Solution for Question #1 (¢ ae J, — te is Ye Lng! aASSune Page | of 5 bi = => Question #2 (10 points) Muay a1 q) a iy ee oO, Oul=1" LG O° y. : a ge 1) =u17 . @ (Ou 1) 0100 1)" + 10" = (ou fy *. Question #3 (30 points) Let M= (Q. E, qo, F, 5), where O = (qo, qi, 42.93), 2 =0.1}. F=(qs}, and 5 is gives by the following table. “Pung these Jar ages (35 polmes) ~c)*)* and call it M2 aton recognizing L(M1)" ‘ naton recognizing L(M ly LM2) ©) Build an automaton recognizing L(M 1).L(M2), A Dnswer for Question #4