questions-post-midterm

Contents 0 Introduction 5 0 . 1 Bonus points for contributing! 5 0 . 2 Soundness 5 0 . 3 (In)Completeness 5 0 . 4 Syllabus Questions 6 0 . 5 Self-Assessment Questions 9 I Pre-Midterm 11 1 Grammar Derivations 13 1 . 1 Some Regular Languages 13 1 . 2 CFG for Simple Arithmetic Expressions, with Nesting 15 2 Simple Program Understanding 17 2 . 1 Some Simple List Examples 17 2 . 2 Four Variants of Linear Search 19 2 . 3 Introducing Polymorphism 25 3 Recursive Descent Parsing 27 3 . 1 Illustrative Examples 27 3 . 2 More Realistic Questions 30

6 derek + students + staff III Other Stuff 93 12 Short-Answer Questions 95 12 . 1 Computational Complexity 95 12 . 2 Automata 99 12 . 3 Grammars 100 A Epilogue 101

ece351 study questions 9 Exercise 0 . 4 . 10 If you are going to skip a lab, it is better to skip a lab where the code is not re-used by future labs. [T/F] Solution 0 . 4 . 10 T Exercise 0 . 4 . 11 Announcements for this course will be made by: a. carrier pigeon b. bulletin board in hallway c. email d. Piazza Solution 0 . 4 . 11 D Exercise 0 . 4 . 12 The Lab Manual, Course Notes, Outline, slides, etc. , will be distributed by: a. floppy disk b. shared network drive c. email d. hard copy e. Git Solution 0 . 4 . 12 E Exercise 0 . 4 . 13 The Lab Manual, Course Notes, Outline, slides, etc. , will be updated throughout the term. a. Nope, they are set in stone on the first day. b. Yep, everything changes all the time. c. The Outline is fixed at the end of the first week. The other documents will receive minor improvements throughout the term. Solution 0 . 4 . 13 C Exercise 0 . 4 . 14 The weekly lab deadline used to be Sunday at 11 : 59pm . Why are we no longer using that deadline? a. Religious reasons. b. Students would not attend the lab sessions all week. They wouldn’t start the lab until Saturday. Then they would complain that the course staff were not available to help them. Solution 0 . 4 . 14 B Exercise 0 . 4 . 15 The weekly lab deadline used to be Thursday at 11 : 59pm . Why are we proposing to change that deadline? a. Legal reasons. b. Students were complaining too much. c. Students would not attend the lab sessions all week. They wouldn’t start the lab until Thursday 6pm . Then they would complain that the course staff were not available to help them.

1 Grammar Derivations 1 . 1 Some Regular Languages Exercise 1 . 1 . 1 Engineers need to be able to work in both major mea- surement systems. Using the grammar below, derive the input strings metric 3.875 and imperial 3 7/8 . Measurement → ‘ metric ’ DecimalNumber | ‘ imperial ’ FractionalNumber DecimalNumber → Digits ‘ . ’ Digits FractionalNumber → Digits Digits ‘ / ’ Digits Digits → [ 0 - 9 ] + Solution 1 . 1 . 1 One derivation for each input: Measurement → ‘ metric ’ DecimalNumber → ‘ metric ’ Digits ‘ . ’ Digits → ‘ metric ’ ‘ 3 ’ ‘ . ’ ‘ 875 ’ Now the imperial input: Measurement → ‘ imperial ’ FractionalNumber → ‘ imperial ’ Digits Digits ‘ / ’ Digits → ‘ imperial ’ ‘ 3 ’ ‘ 7 ’ ‘ / ’ ‘ 8 ’

ece351 study questions 21 2 . 2 Four Variants of Linear Search Figure 2 . 4 lists four different implementations of linear search. The input, output, and algorithm are the same for all: • Input: a list of strings, where the first one is the token to search for in the rest of the list. • Output: – Normal: prints “found it!” or “didn’t find it” – Errors: if the list is not provided • Algorithm: linear search – Runtime: O(n) – Space consumption: O(n) – Termination: either the token is found or the end of the list is reached. So what’s differs between these four programs? • Static Structure: – Data Structures: arrays vs. linked lists • Dynamic Execution: – Control Structures / Call Graph: iteration vs. recursion E xercise : draw an object diagram of the state of each program when it finds a match given the input ‘Moe Larry Curly Moe’. So- lutions given on subsequent pages in Figures 2 . 5 , 2 . 6 , 2 . 7 , 2 . 8 . 1 / ** An immutable Node structure used for linked 2 * lists in two of the Linear Search variants. * / 3 class Node { 4 final Node next; 5 final String data; 6 Node(Node next, String data) { 7 this .next = next; 8 this .data = data; 9 } 10 } Figure 2 . 3 : Node class used by some variants of Linear Search

22 derek + students + staff 1 public class LinearSearch_Array_Iterative { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 for ( int i = 1; i < args.length; i++) { 5 if (toFind.equals(args[i])) { 6 System.out.println("found it!"); 7 System.exit(0); 8 } 9 } 10 System.out.println("didn’t find it"); 11 System.exit(1); 12 } 13 } 1 public class LinearSearch_Array_Recursive { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 search(toFind, args, 1); 5 System.out.println("didn’t find it"); 6 System.exit(1); 7 } 8 static void search(String toFind, String[] a, int i) { 9 if (toFind.equals(a[i])) { 10 System.out.println("found it!"); 11 System.exit(0); 12 } else { 13 if (i < a.length-1) search(toFind, a, i+1); 14 } 15 } 16 } 1 public class LinearSearch_Objects_Iterative { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 // copy array to linked list 5 Node head = null ; 6 for ( int i = args.length-1; i > 0; i--) { 7 head = new Node(head, args[i]); 8 } 9 // now search 10 Node n = head; 11 while (n != null ) { 12 if (toFind.equals(n.data)) { 13 System.out.println("found it!"); 14 System.exit(0); 15 } else { 16 n = n.next; 17 } 18 } 19 // search is over: unsuccessfull 20 System.out.println("didn’t find it"); 21 System.exit(1); 22 } 23 } 1 public class LinearSearch_Objects_Recursive { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 // copy array to linked list 5 Node head = null ; 6 for ( int i = args.length-1; i > 0; i--) { 7 head = new Node(head, args[i]); 8 } 9 // now search 10 search(toFind, head); 11 // search is over: unsuccessfull 12 System.out.println("didn’t find it"); 13 System.exit(1); 14 } 15 static void search(String toFind, Node n) { 16 if (n == null ) { return ; } 17 else { 18 if (toFind.equals(n.data)) { 19 System.out.println("found it!"); 20 System.exit(0); 21 } else { 22 search(toFind, n.next); 23 } 24 } 25 } 26 } Figure 2 . 4 : Four different implementa- tions of linear search.

ece351 study questions 23 L inear S earch : A rray +I terative V ariant • Recall that the input string, provided on the command line for this execution, is ‘Moe Larry Curly Moe’. Exercise 2 . 2 . 1 1 public class LinearSearch_Array_Iterative { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 for ( int i = 1; i < args.length; i++) { 5 if (toFind.equals(args[i])) { 6 System.out.println("found it!"); 7 System.exit(0); 8 } 9 } 10 System.out.println("didn’t find it"); 11 System.exit(1); 12 } 13 } Solution 2 . 2 . 1 PC: 6 main() args toFind i = 3 array1 Moe 0 3 Larry 1 Curly 2 Figure 2 . 5 : Object diagram for iterative array variant of linear search when it finds ‘Moe’ in ‘Larry Curly Moe’.

24 derek + students + staff L inear S earch : A rray +R ecursive V ariant • Recall that the input string, provided on the command line for this execution, is ‘Moe Larry Curly Moe’. • Here we see three stack frames corresponding to the search() method, one of which originates from main() , and the other two of which are recursive calls where search() calls itself. Exercise 2 . 2 . 2 1 public class LinearSearch_Array_Recursive { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 search(toFind, args, 1); 5 System.out.println("didn’t find it"); 6 System.exit(1); 7 } 8 static void search(String toFind, String[] a, int i) { 9 if (toFind.equals(a[i])) { 10 System.out.println("found it!"); 11 System.exit(0); 12 } else { 13 if (i < a.length-1) search(toFind, a, i+1); 14 } 15 } 16 } Solution 2 . 2 . 2 PC: 10 main() args toFind search() toFind a i = 1 array1 Moe search() toFind a i = 2 search() toFind a i = 3 0 3 Larry 1 Curly 2 Figure 2 . 6 : Object diagram for recursive array variant of linear search when it finds ‘Moe’ in ‘Larry Curly Moe’.

ece351 study questions 25 L inear S earch : O bjects +I terative V ariant • Recall that the input string, provided on the command line for this execution, is ‘Moe Larry Curly Moe’. • The linked list of Nodes needs to be constructed from the back because it is immutable and its next pointer points forwards: there- fore, we cannot construct a Node until we have already constructed the other Node that comes after it in the list. • The source code for Node is above in Figure 2 . 3 . Exercise 2 . 2 . 3 1 public class LinearSearch_Objects_Iterative { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 // copy array to linked list 5 Node head = null ; 6 for ( int i = args.length-1; i > 0; i--) { 7 head = new Node(head, args[i]); 8 } 9 // now search 10 Node n = head; 11 while (n != null ) { 12 if (toFind.equals(n.data)) { 13 System.out.println("found it!"); 14 System.exit(0); 15 } else { 16 n = n.next; 17 } 18 } 19 // search is over: unsuccessfull 20 System.out.println("didn’t find it"); 21 System.exit(1); 22 } 23 } Solution 2 . 2 . 3 PC: 13 main() args toFind head i n array1 Moe Node1 Node3 0 3 Larry 1 Curly 2 Node2 Figure 2 . 7 : Object diagram for iterative linked-list variant of linear search when it finds ‘Moe’ in ‘Larry Curly Moe’.

26 derek + students + staff L inear S earch : O bjects +R ecursive V ariant • Recall that the input string, provided on the command line for this execution, is ‘Moe Larry Curly Moe’. • Here we see three stack frames corresponding to the search() method, one of which originates from main() , and the other two of which are recursive calls where search() calls itself. • The linked list of Nodes needs to be constructed from the back because it is immutable and its next pointer points forwards: there- fore, we cannot construct a Node until we have already constructed the other Node that comes after it in the list. • The source code for Node is above in Figure 2 . 3 . Exercise 2 . 2 . 4 1 public class LinearSearch_Objects_Recursive { 2 public static void main(String[] args) { 3 String toFind = args[0]; 4 // copy array to linked list 5 Node head = null ; 6 for ( int i = args.length-1; i > 0; i--) { 7 head = new Node(head, args[i]); 8 } 9 // now search 10 search(toFind, head); 11 // search is over: unsuccessfull 12 System.out.println("didn’t find it"); 13 System.exit(1); 14 } 15 static void search(String toFind, Node n) { 16 if (n == null ) { return ; } 17 else { 18 if (toFind.equals(n.data)) { 19 System.out.println("found it!"); 20 System.exit(0); 21 } else { 22 search(toFind, n.next); 23 } 24 } 25 } 26 } Solution 2 . 2 . 4 PC: 19 main() args toFind head i = 0 search() toFind n array1 Moe Node3 search() toFind n search() toFind n Node2 Node1 0 3 Larry 1 Curly 2 Figure 2 . 8 : Object diagram for recursive linked-list variant of linear search when it finds ‘Moe’ in ‘Larry Curly Moe’.

ece351 study questions 27 2 . 3 Introducing Polymorphism Exercise 2 . 3 . 1 Consider the following code listing, which is a simpli- fied version of the ast code in the labs for language F . Demonstrate your understanding of this code by drawing a class diagram, an ob- ject diagram for time point (PC= 29 and i= 2 ), and by describing the input, output, and polymorphic method call targets. Solution 2 . 3 . 1 • Input: none • Output: and null and null or null or null and null and null • Polymorphic Call Targets Line 28 : i target 0 AndExpr.operator() 1 OrExpr.operator() 2 AndExpr.operator() Class Diagram: Expr BinaryExpr AndExpr OrExpr PC: 29 main() args b a i = 2 e array1 AndExpr1 AndExpr2 0 2 OrExpr1 1 1 abstract class Expr { 2 abstract String operator(); 3 } 4 abstract class BinaryExpr extends Expr { 5 final Expr left; 6 final Expr right; 7 abstract BinaryExpr newBinaryExpr(Expr l, Expr r); 8 public String toString() { return left + operator() + right; } 9 } 10 final class AndExpr extends BinaryExpr { 11 String operator() { return " and "; } 12 BinaryExpr newBinaryExpr(Expr l, Expr r) { return new AndExpr(l,r); } 13 } 14 final class OrExpr extends BinaryExpr { 15 String operator() { return " or "; } 16 BinaryExpr newBinaryExpr(Expr l, Expr r) { return new OrExpr(l,r); } 17 } 18 final class Main { 19 public static void main(String[] args) { 20 BinaryExpr b = new AndExpr(); // why isn’t the type of e AndExpr? 21 Expr[] a = new Expr[3]; // an empty array of size 3 22 // what is the type of the object stored in each element of the array? 23 a[0] = b; 24 a[1] = new OrExpr(); 25 a[2] = b.newBinaryExpr( null , null ); // monomorphic call site 26 for ( int i = 0; i < a.length; i++) { 27 Expr e = a[i]; 28 System.out.println(e.operator()); // polymorphic call site 29 System.out.println(e.toString()); // mono or polymorphic? 30 } 31 } 32 }

3 Recursive Descent Parsing We originally learned this technique in lab1 , and then practiced it again in lab3 . Recursive descent parsing is a programming technique for writing a parser by hand, given a grammar. A grammar is a mathematical specification for a language. We can also consider it as a mathemat- ical specification for a parser. Using the recursive descent parsing technique, we can systematically derive the code for the parser (rec- ognizer) from the grammar using the following rules: These kinds of questions might ask you to write a recognizer , parser , or evaluator : recognizer: string → boolean parser: string → ast evaluator: string → value A recognizer might appear to return void, following the convention in the labs, where the lexer will throw an exception if asked to consume a token that isn’t there: i.e. , exception is reject, and regular completion is accept. Grammar Feature 7→ Code non-terminal 7→ method terminal 7→ Lexer.consume() repetition (*, +) 7→ loop alternation ( | ) 7→ if For these kinds of questions, the answers are just pseudo-code. What we are looking for is that you understand the technique — we aren’t picky about syntactically perfect code. You can assume a lexer like the one we have used in the labs. 3 . 1 Illustrative Examples Exercise 3 . 1 . 1 A list of names: List → Name * Name → ID Solution 3 . 1 . 1 void List() { // a method for the non-terminal List while (!lexer.inspectEOF()) { // a loop for the * Name(); // the rule for List uses Name, so we get a call here } lexer.consumeEOF(); } void Name() { // a method for the non-terminal Name lexer.consumeID(); }

30 derek + students + staff Exercise 3 . 1 . 2 Engineers need to be able to work in both major mea- surement systems: Measurement → ‘ metric ’ DecimalNumber | ‘ imperial ’ FractionalNumber DecimalNumber → Digits ‘ . ’ Digits FractionalNumber → Digits Digits ‘ / ’ Digits Digits → [ 0 - 9 ] + Solution 3 . 1 . 2 void Measurement() { // a method for the non-terminal if (lexer.inspect("metric")) { // if for the | (bar) lexer.consume("metric"); DecimalNumber(); } else if (lexer.inspect("imperial")) { // or, in fancy talk: conditional for the alternation lexer.consume("imperial"); FractionalNumber(); } else { // reject: unknown case throw new RuntimeException(("measurement system unrecognized: " + lexer.next()); } lexer.consumeEOF(); } void DecimalNumber() { // a method for the non-terminal lexer.consumeDigits(); lexer.consume("."); lexer.consumeDigits(); } void FactionalNumber() { // a method for the non-terminal lexer.consumeDigits(); lexer.consumeDigits(); lexer.consume("/"); lexer.consumeDigits(); }

ece351 study questions 31 Exercise 3 . 1 . 3 Who does what: Sentences in this language include: Engineer calculates design Physician examines patient Judge decides case ProfessionalSkills → Technical | Medical | Legal Technical → (‘ Engineer ’ ‘ calculates ’ | ‘ Architect ’ ‘ draws ’) ‘ design ’ Medical → (‘ Physician ’ ‘ examines ’ | ‘ Surgeon ’ ‘ cuts ’) ‘ patient ’ Legal → (‘ Lawyer ’ ‘ advocates ’ | ‘ Judge ’ ‘ decides ’) ‘ case ’ Solution 3 . 1 . 3 void ProfessionalSkills() { // a method for the non-terminal if (lexer.inspect("Engineer") || lexer.inspect("Architect")) { Technical(); } else if (lexer.inspect("Physician") || lexer.inspect("Surgeon")) { Medical(); } else if (lexer.inspect("Lawyer") || lexer.inspect("Judge")) { Legal(); } else { thrown new RuntimeException("unknown profession: " lexer.next()); } lexer.consumeEOF(); } void Technical() { // a method for the non-terminal if (lexer.inspect("Engineer")) { lexer.consume("Engineer"); lexer.consume("caclulates"); } else if (lexer.inspect("Architect")) { lexer.consume("Architect"); lexer.consume("draws"); } lexer.consume("design"); } void Medical() { // a method for the non-terminal if (lexer.inspect("Physician")) { lexer.consume("Physician"); lexer.consume("examines"); } else if (lexer.inspect("Surgeon")) { lexer.consume("Surgeon"); lexer.consume("cuts"); } lexer.consume("patient"); } void Legal() { // a method for the non-terminal if (lexer.inspect("Lawyer")) { lexer.consume("Lawyer"); lexer.consume("advocates"); } else if (lexer.inspect("Judge")) { lexer.consume("Judge"); lexer.consume("decides"); } lexer.consume("case"); }

32 derek + students + staff 3 . 2 More Realistic Questions Exercise 3 . 2 . 1 An ll ( 1 ) arithmetic calculator grammar with binary operators, operator precedence, and expression nesting: The grammar in the question is a left- factored variant of this grammar: S → Expr Expr → Term ‘ + ’ Expr | Term Term → Factor ‘ * ’ Expr | Factor Factor → Int | ‘ ( ’ Expr ‘ ) ’ S → Expr Expr → Term TermTail TermTail → ‘ + ’ Expr | e Term → Factor FactorTail FactorTail → ‘ * ’ Expr | e Factor → Int | ‘ ( ’ Expr ‘ ) ’ Solution 3 . 2 . 1 Recognizer: void S() { Expr(); } void Expr() { Term(); TermTail(); } void Term() { Factor(); FactorTail(); } void Factor() { if (lexer.inspect("(")) { lexer.consume("("); Expr(); lexer.consume(")"); } else { lexer.consumeInt(); } } void TermTail() { if (lexer.inspect("+")) { lexer.consume("+"); Expr(); } } void FactorTail() { if (lexer.inspect(" * ")) { lexer.consume(" * "); Expr(); } } Evaluator: int S() { return Expr(); } int Expr() { return Term() + TermTail(); } int Term() { return Factor() * FactorTail(); } int Factor() { if (lexer.inspect("(")) { lexer.consume("("); int e = Expr(); lexer.consume(")"); return e; } else { return lexer.consumeInt(); } } int TermTail() { if (lexer.inspect("+")) { lexer.consume("+"); return Expr(); } else { return 0; } // epslion: use identity element for addition } int FactorTail() { if (lexer.inspect(" * ")) { lexer.consume(" * "); return Expr(); } else { return 1; } // epsilon: use identity element for multiplication }

4 Finite Automata & Regular Languages 4 . 1 Automata Execution Execution abc: in states a 1 → 2 b 2 → 1 c 1 → 2 out accept Execution ab: in states a 1 → 2 b 2 → 1 out reject Execution acb: in states a 1 → 2 c 2 → X b X → X out reject input tape machine states storage output tape a b c 1 2 accept b a,c Execution ac: in states a 1 → 2 – 2 → 1 c 1 → 2

34 derek + students + staff input tape machine states storage output tape a c 1 2 accept epsilon a,c

ece351 study questions 35 4 . 2 Design a Regular Language Exercise 4 . 2 . 1 Consider a language where real numbers are defined as follows: a real constant contains a decimal point or E notation, or both. For example, 0 . 01 , 2 . 7834345 , ∼ 1 . 2 E 12 , and 7 E ∼ 5 , 35 . are real constants. The symbol " ∼ " denotes unary minus and may appear before the number or on the exponent. There is no unary "+" opera- tion. There must be at least one digit to the left of the decimal point, but there might be no digits to the right of the decimal point. The exponent following the "E" is a (possibly negative) integer. Write a regular expression (RE) for such real constants. You may use any of the EBNF extended notation. Solution 4 . 2 . 1 Constraints on real constant: • contains a decimal point, E notation , or both • unary minus may appear before the number or an exponent • no unary plus • at least one digit to the left of decimal point • zero or more digits to the right of the decimal point • exponent following ‘E’ is an integer Therefore, a regular expression that matches this definition is as follows: ∼ ? [ 0 - 9 ] + ( ( . [ 0 - 9 ] * ( E ∼ ? [ 0 - 9 ] + ) ? ) | ( E ∼ ? [ 0 - 9 ] + ) )

36 derek + students + staff Exercise 4 . 2 . 2 In a certain (fictional) programming language, assign- ment statements are described as: • An assignment statement may have an optional label at the start of the statement. • The assignment statement itself consists of an identifier, followed by the assignment operator, followed by an arithmetic expression and ending with the statement termination operator. • A label consists of one or more letters (no digits), followed by a colon (:). • An identifier starts with a letter which may be followed by any number of letters or digits. • The assignment operator is the equal sign (=). • Arithmetic expressions consist of one or more identifiers, sepa- rated by arithmetic operators. • The arithmetic operators are: + , - , × , ÷ . • The statement termination operator is the semicolon (;). Write a regular expression to recognize assignment statements for this language. Solution 4 . 2 . 2 L = a | b | c | ... | z D = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ( LL * : | e ) L ( L | D ) * = L ( L | D ) * ((+ | - | × |÷ ) L ( L | D ) * ) * ; Exercise 4 . 2 . 3 Write a regular expression that describes floating point numbers. These examples should be accepted by your solution: 1 . 2 , 0 . 004 , . 5 , 0 , - 76 . 45 , -. 12 , 87 , + 2 . 2 , +. 3 Solution 4 . 2 . 3 (-|+)?[0-9] * \.?[0-9] * Note: do not require the backslash before the period in student solutions

ece351 study questions 37 4 . 3 Draw an NFA Exercise 4 . 3 . 1 Draw NFA for the following notations used in ex- tended regular expressions: a. R ? that matches zero or one copy of R b. R + that matches one or more copies of R Solution 4 . 3 . 1 Source: Question 4 at from-students/omortaza _ problem _ set.pdf Exercise 4 . 3 . 2 Draw an NFA for (a|b) * a(a|b) 3 Solution 4 . 3 . 2 Source: Question 4 at from-students/sj2choi-dfa-nfa. pdf Exercise 4 . 3 . 3 Construct (draw) a Non-deterministic Finite Automa- ton (NFA) to recognize the regular expression: ((( a | b ) bb * ) * | aa * )(( a | b ) ab ) * Solution 4 . 3 . 3 Source: Question 2 .b at ece251/ECE251MS00P.pdf 4 . 4 NFA to DFA Exercise 4 . 4 . 1 Consider the following NFA, whose final state is state 8 . Convert the NFA into a DFA, and draw the resulting DFA. Indicate which state(s) of the DFA are final states. Dotted edges are epsilon ( e ) edges. 1 2 5 3 a 6 a b 4 b 7 b 8 a b Solution 4 . 4 . 1 X: 1, 2, 3, 5 Y: 3, 6, 8 a Z: 4, 5, 2, 3 b W: 2, 4, 5, 3, 7 b a b a b

38 derek + students + staff 4 . 5 DFA Minimization Exercise 4 . 5 . 1 Minimize the number of states in the following DFA. Draw the resulting optimized DFA. All states of the initial DFA are final states. Dotted edges are epsilon ( e ) edges. 1 2 b 4 a 3 a 5 b b a 6 a,b a,b Solution 4 . 5 . 1 W: 5, 6 a,b X: 1, 3 Y: 4 a Z: 2 b b a

ece351 study questions 39 4 . 6 Flavours of Non-Determinism Consider the following NFA that starts at state 1 and accepts at state 3 (but gets stuck at state 2 ): zero 1 2 x 3 x Exercise 4 . 6 . 1 If we assume angelic non-determinism, and the ma- chine receives input string ‘x’, which state will it transition to? Solution 4 . 6 . 1 3 Exercise 4 . 6 . 2 If we assume demonic non-determinism, and the ma- chine receives input string ‘x’, which state will it transition to? Solution 4 . 6 . 2 2 Exercise 4 . 6 . 3 If we assume arbitrary non-determinism, and the machine receives input string ‘x’, which state will it transition to? Solution 4 . 6 . 3 either 2 or 3

40 derek + students + staff Exercise 4 . 6 . 4 HTML is the standard language for describing web pages. Can a regular expression for recognizing HTML be written? Why or why not? Here is an example fragment of HTML: < html > < head >< title >Web Page Title</ title ></ head > < body > It’s a web page! </ body > </ html > Solution 4 . 6 . 4 No, HTML is not a regular language because it has nested tags.

ece351 study questions 41 4 . 7 Really Difficult Automata Design Question Exercise 4 . 7 . 1 Consider the usual string representation of binary in- tegers. The most significant bit is on the left, and the least significant bit is on the right. For example, ‘ 10 ’ is 2 , and ‘ 100 ’ is 4 . Leading zeros are permitted, e.g. ‘ 0010 ’ is also 2 . Write a regular expression that accepts all binary integers that are divisible by 5 . The general technique for writing a dfa to check if a binary number is divisible by n is available online, e.g. : http://stackoverflow. com/questions/21897554/ design-dfa-accepting-binary-strings-divisible-by-a Solution 4 . 7 . 1 This question is too hard. It should have been phrased to write a dfa , instead of a regex. If you know the technique it is not hard to make the dfa . Set states to be the remainders. Define the transition function δ ( s , α ) to be δ ( s , 0 ) = ( 2 s ) %5 and δ ( s , 1 ) = ( 2 s + 1 ) %5 . Solid lines are 1 -transitions and dotted lines are 0 -transitions. 0 1 2 3 4 Different people have come up with different regexs that are equivalent to this dfa . Converting a dfa to a regex is not hard in principle, but this one is large in practice. http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions Here is the short one: [ 0 + 1 ( 11 + 0 ) ( 01 * 01 )* 1 ]* Here is the full derivation of the long one: Q 0 = 0 Q 0 ∪ 1 Q 1 ( 4 . 1 ) Q 1 = 0 Q 2 ∪ 1 Q 3 ( 4 . 2 ) Q 2 = 0 Q 4 ∪ 1 Q 0 ( 4 . 3 ) Q 3 = 0 Q 1 ∪ 1 Q 2 ( 4 . 4 ) Q 4 = 1 Q 4 ∪ 0 Q 3 ( 4 . 5 ) First simplify 4 . 5 , Q 4 = 1 * ∪ 0 Q 3 ( 4 . 6 )

42 derek + students + staff Apply 4 . 4 and 4 . 6 to 4 . 3 Q 2 = 0 Q 4 ∪ 1 Q 0 = 01 * ∪ 00 Q 3 ∪ 1 Q 0 = 01 * ∪ 000 Q 1 ∪ 001 Q 2 ∪ 1 Q 0 = 01 * ∪ ( 001 ) * ∪ 000 Q 1 ∪ 1 Q 0 ( 4 . 7 ) Apply 4 . 7 and 4 . 4 to 4 . 2 Q 1 = 0 Q 2 ∪ 1 Q 3 = 0 Q 2 ∪ 10 Q 1 ∪ 11 Q 2 = ( 10 ) * ∪ ( 0 ∪ 11 ) Q 2 = ( 10 ) * ∪ ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ∪ 000 Q 1 ∪ 1 Q 0 ] = ( 10 ) * ∪ ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ∪ 1 Q 0 ] ∪ ( 0 ∪ 11 ) 000 Q 1 = ( 10 ) * ∪ [( 0 ∪ 11 ) 000 ] * ∪ ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ∪ 1 Q 0 ] ( 4 . 8 ) Apply 4 . 8 to 4 . 1 Q 0 = 0 Q 0 ∪ 1 Q 1 = 0 * ∪ 1 ( 10 ) * ∪ 1 [( 0 ∪ 11 ) 000 ] * ∪ 1 ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ∪ 1 Q 0 ] = 0 * ∪ 1 ( 10 ) * ∪ 1 [( 0 ∪ 11 ) 000 ] * ∪ 1 ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ] ∪ 1 ( 0 ∪ 11 ) 1 Q 0 = [ 1 ( 0 ∪ 11 ) 1 ] * ∪ 0 * ∪ 1 ( 10 ) * ∪ 1 [( 0 ∪ 11 ) 000 ] * ∪ 1 ( 0 ∪ 11 )[ 01 * ∪ ( 001 ) * ] 4 . 8 Unanswered Automata Design Produce NFAs that recognize the following regular expressions. Convert the NFAs to DFAs and minimize them. Exercise 4 . 8 . 1 xy * ( z | cw ) ab ? Solution 4 . 8 . 1 TBD Exercise 4 . 8 . 2 ( rmb | c ) ? ( ns f ) * Solution 4 . 8 . 2 TBD

ece351 study questions 43 4 . 9 Automata Design related to W Recall the W language for Boolean waveforms from the labs. Imagine that we extend this language for a three-valued logic: true, false, and unknown. Here is a regular expression for this new language. Complete each construction and transformation. (U|F|T) * Exercise 4 . 9 . 1 Regex → NFA Solution 4 . 9 . 1 Dotted, unlabelled edges are epsilon edges. 1 8 2 3 4 5 U 6 F 7 T Exercise 4 . 9 . 2 NFA → DFA Solution 4 . 9 . 2 A: 1, 2, 3, 4, 8 B: 5, 8, 1, 2, 3, 4 U C: 6, 8, 1, 2, 3, 4 F D: 7, 8, 1, 2, 3, 4 T U F T U F T U F T Exercise 4 . 9 . 3 DFA → minimized DFA Solution 4 . 9 . 3 ABCD U F T

5 Grammar Analysis & Design 5 . 1 Grammar Refactoring C onsider the following grammar . S → E E → E - E | INT Exercise 5 . 1 . 1 Show that this grammar is ambiguous. Solution 5 . 1 . 1 Input string ‘ 3 - 2 - 1 ’ parses as either ‘( 3 - 2 )- 1 ’ or ‘ 3 -( 2 - 1 )’. Exercise 5 . 1 . 2 Refactor the grammar to remove the ambiguity (and to produce arithmetically correct results with the AST is evaluated). Solution 5 . 1 . 2 S → E E → E - INT | INT

46 derek + students + staff Exercise 5 . 1 . 3 This is from an old ece251 midterm. We did not study ll ( 1 ) parsing tables in ece351 . It’s just a tabular representa- tion of the predict sets. The following grammar is not suitable for a top-down predictive parser. Fix the problems by rewriting the grammar (with any required changes) and then construct the ll ( 1 ) parsing table for your new grammar. L → R ‘ a ’ L → Q ‘ ba ’ R → ‘ aba ’ R → ‘ caba ’ R → R ‘ bc ’ Q → ‘ bbc ’ Q → ‘ bc ’ Solution 5 . 1 . 3 There are a few issues with this grammar that we should resolve: • Left recursion of the production R → R bc • Unpredictability of Q given one look ahead token because of com- mon prefix Left Recursion: R → ‘ aba ’ R → ‘ caba ’ R → R ‘ bc ’ Introduce additional non-terminal R 0 : R’ → ‘ bc ’ R’ | e and rewrite the productions for R : R → ‘ aba ’ R’ R → ‘ caba ’ R’ Common Prefix: Q → ‘ bbc ’ Q → ‘ bc ’ We can left factor Q to remove the common prefix b by introduc- ing the non-terminal Q tail : Q → ‘ b ’ Q tail Q tail → ‘ bc ’ | ‘ c ’ Our final grammar is: L → R ‘ a ’ L → Q ‘ ba ’ R → ‘ aba ’ R’ R → ‘ caba ’ R’ R’ → ‘ bc ’ R’ R’ → e Q → ‘ b ’ Q tail Q tail → ‘ bc ’ Q tail → ‘ c ’ Exercise 5 . 1 . 4 Refactor the following grammar to ll ( 1 ) form. S → id ‘ ( ’ A ‘ ) ’ | id ‘ [ ’ A ‘ ] ’ A → A ‘ , ’ id | id

ece351 study questions 47 Solution 5 . 1 . 4 S → id T T → ‘ ( ’ A ‘ ) ’ | ‘ [ ’ A ‘ ] ’ A → id U U → ‘ , ’ id U | e

48 derek + students + staff 5 . 2 LL( 1 ) Analysis Exercise 5 . 2 . 1 Also from an old ece251 midterm. Consider the grammar given below, with S as the start symbol, and a , b , c , d , f and g as terminals. S → XYZ $$ X → ‘ a ’ | Z ‘ b ’ | e Y → ‘ c ’ | ‘ d ’ XY | e Z → ‘ f ’ | ‘ g ’ Compute the FIRST and FOLLOW sets for each non-terminal in the grammar. Solution 5 . 2 . 1 Recall that EPS, FIRST, FOLLOW, and PREDICT sets are defined as follows: EPS ( α ) ≡ if α = ⇒ * e then true else false FIRST ( α ) ≡ { c : α = ⇒ * c β } FOLLOW ( A ) ≡ { c : S = ⇒ + α A c β } PREDICT ( A → α ) ≡ FIRST ( α ) ∪ ( if EPS ( α ) then FOLLOW ( A ) else ∅ ) Non-terminal Equation Solution Comment eps ( S ) = 0 = 0 contains a terminal ($$) eps ( X ) = 1 = 1 derives e directly eps ( Y ) = 1 = 1 derives e directly eps ( Z ) = 0 = 0 derives terminals Non-terminal Equation Solution Comment first ( S ) = first ( X ) ∪ first ( Y ) ∪ first ( Z ) = { ‘ a 0 , ‘ c 0 , ‘ d 0 , ‘ f 0 , ‘ g 0 } X and Y are nullable first ( X ) = { ‘ a 0 } ∪ first ( Z ) = { ‘ a 0 , ‘ f 0 , ‘ g 0 } two non- e options first ( Y ) = { ‘ c 0 , ‘ d 0 } = { ‘ c 0 , ‘ d 0 } two non- e options first ( Z ) = { ‘ f 0 , ‘ g 0 } = { ‘ f 0 , ‘ g 0 } two non- e options Non-terminal Equation Solution Comment follow ( S ) = ∅ = ∅ follow ( X ) = first ( Y ) ∪ follow ( Y ) = { ‘ c 0 , ‘ d 0 , ‘ f 0 , ‘ g 0 } S → XYZ $$; Y → ‘ d 0 XY ( Y is nullable) follow ( Y ) = first ( Z ) = { ‘ f 0 , ‘ g 0 } S → XYZ $$ follow ( Z ) = { ‘ b 0 , $$ } = { ‘ b 0 , $$ } S → XYZ $$; X → Z ‘ b 0

ece351 study questions 49 Exercise 5 . 2 . 2 Assume the grammar shown below, with expr as the start sym- bol, and that terminal id can be any single letter of the alphabet ( a through z ). expr → ‘ id ’ “ := ” expr expr → term term_tail term_tail → “ + ” term term_tail | e term → factor factor_tail factor_tail → “ * ” factor factor_tail | e factor → “ ( ” expr “ ) ” | ‘ id ’ In two or three sentences, explain why the grammar cannot be parsed by an LL( 1 ) parser. Solution 5 . 2 . 2 The problem originates from the non-terminal expr . The productions expr → ‘ id ’ “ := ” expr expr → term term_tail actually have common prefixes (The latter production for expr may derive ‘ id ’ as its first terminal: expr → term . . . term → factor . . . factor → ‘ id ’), so an LL( 1 ) parser cannot predict the production to take for the non-terminal expr .

50 derek + students + staff I s the following grammar ll ( 1 )? Prove your answer by com- puting the eps , first , follow and predict sets. Provide both the equations and their solutions, as we studied in class. Note: You may start from the predict sets and work backwards, computing only the first and follow sets that you need. S → (AB|Cx)$$ A → y * B → Cq C → pC| e Exercise 5 . 2 . 3 Convert to bnf Solution 5 . 2 . 3 G → AB$$ G → Cx$$ A → yA A → e B → Cq C → pC C → e Exercise 5 . 2 . 4 eps Solution 5 . 2 . 4 Nonterminal Result Reason eps (G) = 0 $$ is a terminal eps (A) = 1 goes to e directly eps (B) = 0 q is a terminal eps (C) = 1 goes to e directly Exercise 5 . 2 . 5 first Solution 5 . 2 . 5 Nonterminal Equation Solution first (G) = first (A) ∪ first (B) ∪ first (C) ∪ {x} = {p,q,x,y} first (A) = {y} = {y} first (B) = first (C) ∪ {q} = {p,q} first (C) = {p} = {p} Exercise 5 . 2 . 6 follow Solution 5 . 2 . 6

ece351 study questions 51 Nonterminal Equation Solution follow (G) = ∅ = ∅ follow (A) = first (B) = {p,q} follow (B) = {$$} = {$$} follow (C) = {q,x} = {q,x} Exercise 5 . 2 . 7 predict Solution 5 . 2 . 7 Production Equation Solution predict (G → AB$$) = first ( AB$$ ) = first (A) ∪ first (B) = {p,q,y} predict (G → Cx$$) = first (Cx) = first (C) ∪ {x} = {p,x} predict (A → yA) = {y} = {y} predict (A → e ) = follow (A) = {p,q} predict (B → Cq) = first (Cq) = first (C) ∪ {q} = {p,q} predict (C → pC) = {p} = {p} predict (C → e ) = follow (C) = {q,x} Exercise 5 . 2 . 8 Is this grammar ll ( 1 )? Why or why not? Solution 5 . 2 . 8 No. We can predict A , B , and C with one token of lookahead, but not G : the two G productions both have ‘p’ in their predict sets. Consider the input strings ‘pq’ and ‘px’: we need to lookahead two characters to the ‘q’ or the ‘x’ to determine which G production to use.

52 derek + students + staff 5 . 3 Refactoring & LL( 1 ) Proof Together Referring to people by their middle name is also common in families of British ancestry. In many Hispanic countries it is common to name boys ‘Jesus’. The English abbreviation for ‘William’ is ‘Wm’, as in ‘Wm Shake- speare’. I n some countries , such as Bangladesh, there is a practice to give sons the formal first name Mohammed, but then always refer to them by a middle name. In these cases, the formal first name might be abbreviated as ‘Md’ to indicate that it is not for common use. Suppose that we have the following grammar for boys names: S → Md Anwar Sadat S → Md Hosni Mubarak S → Md Siad Barre S → Md Zia-ul-Haq S → Md Ayub Khan S → Md Nawaz Sharif Exercise 5 . 3 . 1 Is this grammar LL( 1 )? Why? Why not? Solution 5 . 3 . 1 No, this grammar is not LL( 1 ) because of common prefixes . If we are expecting to derive S and we look ahead one token and see ‘Md’ then we will not know which rule we are in. Exercise 5 . 3 . 2 Refactor to an equivalent grammar that is LL( 1 ). Solution 5 . 3 . 2 S → Md Tail Tail → Anwar Sadat Tail → Hosni Mubarak Tail → Siad Barre Tail → Zia-ul-Haq Tail → Ayub Khan Tail → Nawaz Sharif Exercise 5 . 3 . 3 Prove this grammar is LL( 1 ). Start with the Predict sets, and compute other sets as necessary. Construct equations sym- bolically before providing concrete answers. Solution 5 . 3 . 3 Predict(S → Md Tail) = {Md} Predict(Tail → Anwar Sadat) = First(Anwar Sadat) = {Anwar} Predict(Tail → Hosni Mubarak = First(Hosni Mubarak) = {Hosni} Predict(Tail → Siad Barre) = First(Siad Barre) = {Siad} Predict(Tail → Zia-ul-Haq) = First(Zia-ul-Haq) = {Zia-ul-Haq} Predict(Tail → Ayub Khan) = First(Ayub Khan) = {Ayub} Predict(Tail → Nawaz Sharif) = First(Nawaz Sharif) = {Nawaz}

ece351 study questions 53 5 . 4 Precedence Exercise 5 . 4 . 1 Consider the expression represented by the following expression tree. Assume that A, B, C, D and E are binary operators. Consider the following infix expression: 3 C 4 B 1 A 2 D 6 B 7 E 5 . Tree [.A [.B [.C 3 4 ] 1 ] [.D 2 [.E [.B 6 7 ] 5 ] ] ] Assume this expression generates the tree shown. Given that all operators have different precedences, and that the operators are non- associative, list the operators A, B, C, D and E in order from highest to lowest precedence. If there is more than one possible answer list them all. Solution 5 . 4 . 1 Precedence: • C has higher precedence than B • B has higher precedence than A • B has higher precedence than E • E has higher precedence than D • D has higher precedence than A Highest to lowest precedence: C B E D A

54 derek + students + staff 5 . 5 Ambiguity C onsider the following ambiguous grammar : E → E ‘ + ’ E | E ‘ * ’ E | int Exercise 5 . 5 . 1 Give an input string with two different legal parse trees in this grammar. Show the parse trees. Solution 5 . 5 . 1 1 + 2 * 3 could parse two ways (as could 1 + 2 + 3 ): ( 1 + 2 ) * 3 1 + ( 2 * 3 ) * + 3 1 2 + 1 * 2 3 Exercise 5 . 5 . 2 Refactor this grammar to have the normal arithmetic precedence and to be right associative. Show the parse tree for your input string above. Solution 5 . 5 . 2 This solution has the precedence correct, but is not right associative, and is ambiguous. E → E ’+’ E E → F F → F ’*’ F F → int 1 + 2 * 3 7→ 1 + ( 2 * 3 ) 1 + 2 + 3 7→ 1 + ( 2 + 3 ) or 7→ ( 1 + 2 ) + 3 This solution is correct on precedence and associativity. It is not ll ( 1 ) , due to common prefixes, but being ll ( 1 ) is not required here. E → F ’+’ E E → F F → int ’*’ F F → int 1 + 2 * 3 7→ 1 + ( 2 * 3 ) 1 + 2 + 3 7→ 1 + ( 2 + 3 ) This solution is correct on precedence and associativity, and is also ll ( 1 ) . S → E $$ E → F P P → + E | e F → int Q Q → * F | e 1 + 2 * 3 7→ 1 + ( 2 * 3 ) 1 + 2 + 3 7→ 1 + ( 2 + 3 ) predict ( P → e ) = follow ( P ) = follow ( E ) = {$$} disjoint from {+} predict ( Q → e ) = follow ( Q ) = follow ( F ) = first (P) ∪ follow ( P ) = {+, $$} disjoint from {*}

6 Grammar Stories 6 . 1 Mary, Mary, Quite Contrary In some places, at some points in time, it has been common to give girls the first name Mary. Suppose that we have the following list of women’s names. (This question is a student-created variant of the ‘Mohammed’ question in the Course Notes.) S → Mary Elizabeth James S → Mary Todd Lincoln S → Mary Queen Scott S → Mary Lynn Monroe S → Mary Tyler Moore Exercise 6 . 1 . 1 Is this grammar LL( 1 )? Why? Why not? Solution 6 . 1 . 1 No, this grammar is not LL( 1 ) because of common prefixes. If we are expecting to derive S and we look ahead one token and see ‘Mary’ then we will not know which rule we are in. Exercise 6 . 1 . 2 Refactor to an equivalent grammar that is LL( 1 ). Solution 6 . 1 . 2 S → Mary Tail Tail → Elizabeth James Tail → Todd Lincoln Tail → Queen Scott Tail → Lynn Monroe Tail → Tyler Moore Exercise 6 . 1 . 3 Prove this grammar is LL( 1 ). Start with the Predict sets, and compute other sets as necessary. Construct equations sym- bolically before providing concrete answers.

56 derek + students + staff Solution 6 . 1 . 3 Production Equation Solution predict (S → Mary Tail) = first (Mary Tail) = {Mary} predict (Tail → Elizabeth James) = first (Elizabeth James) = {Elizabeth} predict (Tail → Todd Lincoln) = first (Todd Lincoln) = {Todd} predict (Tail → Queen Scott) = first (Queen Scott) = {Queen} predict (Tail → Lynn Monroe) = first (Lynn Monroe) = {Lynn} predict (Tail → Tyler Moore) = first (Tyler Moore) = {Tyler} The Predict sets for each non-terminal are all disjoint, so therefore this grammar is LL( 1 ). 6 . 2 As You Like It Rosalind and her cousin Celia cannot agree on how to evaluate the expression ‘ 1 + 2 * 3 ’. Rosalind says it evaluates to 7 , while Celia insists that the answer is 9 . Give the grammar that each heroine has in her head, as well as a derivation showing how the given grammar eval- uates the expression of interest. The grammar should also work for larger expressions with these two operators, but does not need to support nested expressions. 6 . 2 . 1 Rosalind’s Glorious Grammar Rosalind escapes to the Forest of Arden, to enjoy her thoughts away from the annoyance of Duke Frederick’s anger. Sheltered by a sup- portive tree, she quickly jots in her notebook: S → Sum Sum → Sum + Product Sum → Product Product → Product * Int Product → Int She is pleased with the precedence in this, her first grammar of the day: it will indeed bind multiplication tighter than addition. She does a derivation to satisfy herself, and draws the parse tree: + * 1 2 3 S → Sum → Sum + Product → [Product] + [Product * Int] → [Int] + [Int * 3 ] → [ 1 ] + [ 2 * 3 ] But then she realizes that her grammar is not LL( 1 ), and so while it is elegant and correct, it will be difficult to implement. She sees

ece351 study questions 57 that this grammar is left-recursive, which cannot be LL( 1 ). So she left-factors it, as she learned in school: S → Sum Sum → Product STail STail → + Sum | e Product → Int PTail PTail → * Product | e She does a derivation, and draws the parse tree, just to get a better sense of what left-factoring does to her grammar. She writes the epsilons ( e ) in her derivation, just for clarity, even though one would not ordinarily do so. + * 1 2 3 S → Sum → Product STail → [Int PTail] [+ Sum] → [ 1 e ] [+ [Product STail]] → [ 1 ] [+ [[Int PTail] e ]] → [ 1 ] [+ [ 2 [* Product]]] → [ 1 ] [+ [ 2 [* 3 ]]] 6 . 2 . 2 Celia’s Splendid Syntax Celia is no stranger to higher thinking, and her beautiful penmanship attracts the amorous attentions of Oliver. In a moment when Oliver is distracted by giving his younger brother Orlando a hard time, she scribes: S → Product Product → Sum * Product Product → Sum Sum → Int + Sum Sum → Int Meanwhile, a lioness attacks Oliver. Orlando, proving that blood is thicker than water, comes to his brother’s rescue, despite Oliver’s earlier heckling. While the boys are busy getting themselves in to and out of trouble, Celia is happy to derive her thoughts: + 1 2 * 3 S → Product → Sum * Product → [Int + Sum] * [Sum] → [ 1 + Int] * [Int] → [ 1 + 2 ] * [ 3 ] Like her cousin (great minds think alike), Celia realizes that while her

58 derek + students + staff grammar expresses her thoughts about arithmetic precedence to the world, it is not LL( 1 ) — but for a different reason: her syntax suffers from common prefixes. Not one to be outdone, she deftly refactors: S → Product Product → Sum PTail PTail → * Product | e Sum → Int STail STail → + Sum | e And then derives and draws: + * 1 2 3 S → Product → Sum PTail → [Int STail] [* Product] → [ 1 [+ Sum]] [* [Sum PTail]] → [ 1 [+ [Int STail]]] [* [[Int STail] e ]] → [ 1 [+ [ 2 e ]]] [* [[Int STail] e ]] → [ 1 [+ 2 ]] [* [[ 3 e ] e ]] → [ 1 [+ 2 ]] [* 3 ] 6 . 2 . 3 Epilogue In the end, Frederick repents his wicked ways, restoring peace to the duchy. Our heroines decide that, while they fancy Orlando and Oliver respectively, for now they are wedded to their ideas. The brothers eagerly enroll in ece351 in hopes of wooing their sweet- hearts. https://en.wikipedia.org/wiki/As _ You _ Like _ It

Part II Post-Midterm

7 Advanced Program Understanding 7 . 1 Iteration Order Exercise 7 . 1 . 1 list.add(3); list.add(1); list.add(2); System.out.println(list); Solution 7 . 1 . 1 List preserves insertion order: 3 , 1 , 2 Exercise 7 . 1 . 2 tset.add(3); tset.add(1); tset.add(2); System.out.println(tset); Solution 7 . 1 . 2 TreeSet uses the natural ordering: 1 , 2 , 3 Exercise 7 . 1 . 3 hset.add(3); hset.add(1); hset.add(2); System.out.println(hset); Solution 7 . 1 . 3 HashSet has arbitrary iteration order (non-deterministic). There are six possible legal outputs.