CMSC330 - SUMMER 2006 - MIDTERM 1INSTRUCTOR: GUILHERME FONSECA• Write all answers in the answers book provided.• You can keep the exam. Only return the answers book.• You are allowed to consult one letter-size paper, handwritten on one side. Besidesthat, the exam is closed book, closed notes.• There are 8 question, totaling 110 points, in this exam. You have 1 hour and 20minutes to finish it.(1) (20 points) What is the output of each Ruby program below? Ignore any possiblewarning message.(a) puts("ab" +if nil"cd"else"ef"end)(b) a = b = ["c", "a", "b"]a = a.sortputs b(c) a = [1, 2, 3]b = ["x", "y"]c = [a, b, [a, b]]puts c[-1][0](d) h = Hash.new(0)h["a"] = h["b"]h["b"] = 7h["c"] += 2puts "#{h["a"]} #{h["b"]} #{h["c"]}"(2) (10 points) Write a Ruby program that reads several lines from the input, and printsonly the lines that contain exclusively the following characters: uppercase andlowercase letters, digits, and underscore. For example, lines that contain space orpunctuation should not be printed.(3) (21 points) Write a formal regular expression for each of the languages below. Thealphabet is Σ = {a, b}. The only operators allowed are concatenation, ∗ and | (donot write a Ruby regular expression).(a) {w | w begins with a and ends with a }(b) {w | all a’s are immediatly followed by b in w }(c) The union of the two languages above.1(4) (8 points) Write a formal regular expression the language below. The alphabet isΣ = {a, b, c}. The only operators allowed are concatenation, ∗ and | (do not write aRuby regular expression).{w | all consonants are adjacent to a consonant on at least one side in w }Notice that b and c are the only consontants in the alphabet Σ. For example, a,bb, bc, and aabbabcba are in the language, but b, ab, and aba are not.(5) (21 points) Write a DFA for each of the languages below. The alphabet is Σ = {a, b}.(a) {w | w contains at most one b }(b) {w | #a(w) = 0 (mod 2) and #b(w) 6= 0 (mod 3) }(c) {w | w ends with aab}(6) (10 points) Convert the following NFA to a NFA without ε transitions.bSTV WεεεaUbb(7) (10 points) Convert the following NFA without ε transitions to a DFA.STUaabbba(8) (10 points) Convert the following formal regular expression to a
View Full Document