CMSC330 Fall 2009 Quiz #1 Name Discussion Time (circle one): 10am 11am 12pm 1pm 2pm 3pm Do not start this exam until you are told to do so! Instructions • You have 15 minutes for this quiz. • This is a closed book exam. No notes or other aids are allowed. • Answer essay questions concisely using 2-3 sentences. Longer answers are not necessary and a penalty may be applied. • For partial credit, show all of your work and clearly indicate your answers. • Write neatly. Credit cannot be given for illegible answers. 1. (4 pts) What is the output (if any) of the following Ruby program? Write FAIL if code does not execute. a = [1,2,3 ] a[4] = 5 # OUTPUT = a.each{ |x| puts “#{x}” } 2. (4 pts) Is it true that every DFA is a NFA? Explain your answer. 3. (4 pts) Write a DFA that accepts the language 1(00|1)*. You do not need to use the algorithms described in class.4. (8 pts) Begin converting the following NFA into a DFA by applying the subset construction algorithm discussed in class. You do not need to produce the entire DFA. Create at least 2 DFA states (starting state & additional state) and the transition (with label) connecting them. Be sure to list the NFA states represented by each DFA state.
View Full Document
Unlocking...