0 / 0 1 / 20 2 / 25 3 / 20 4 / 25 5 / 20 6 /40 7 /40 8 / 30 9 / 10 10 / 30 TOT / 260 UMBC CMSC 331 Final Exam Section 0101 – December 17, 2002 Name: _________________________________ Student ID#:_____________________________ You will have two hours to complete this closed book exam. We reserve the right to assign partial credit, and to deduct points for answers that are needlessly wordy or simply wrong. 0. Burning rope (0) There are two lengths of rope each of which can burn in exactly one hour. They are not necessarily of the same length or width as each other nor are they of uniform width, thus burning half of the rope will not necessarily take 1/2 hour. By burning the ropes, how do you measure exactly 45 minutes worth of time? ANSWER: If you light both ends of one rope, it will burn in exactly a 1/2 hour. Thus, burn one rope from both ends and the other rope from only one end. Once the one rope (which is burning from both ends) finally burns out (and you know a 1/2 hour has elapsed), you also know that the other rope (which is burning from only one end) has exactly 1/2 hour left to burn. Since you only want 45 minutes, light the second end of the rope. This remaining piece will burn in 15 minutes. Thus, totaling 45 minutes. 1. General multiple-choice questions (20) 1.1 Most modern programming languages use the following schemes for their variable scoping. (a) lexical scoping. (b) dynamic scoping. (c) both lexical and dynamic scoping. (e) scope inferencing. ANSWER: A 1.2 What happens in an assignment such as ``x := y''? (a) The address of x is modified to be the address of y. (b) The address of y is modified to be the address of x. (c) The object bound to y is copied and bound to x, and any previous binding of x to an object is lost. (d) x and y become aliases. (e) the contents of y are copied into the storage allocated to x. ANSWER: D 1.3 Which of the following is true of l-values and r-values? (a) An l-value is a logical value, and an r-value is a real value.. (b) l-values are always to the left of r-values. (c) An l-value refers to a variable’s location while an r-value to its current value. (d) L-values are local and r-values are relative. (e) l-values are static and final whereas r-values are dynamic and extensible. ANSWER C . 1.4 What distinguishes a purely ``functional'' programming language from an ``imperative'' one? (a) There are no variables and hence no assignment operation in a purely functional language. (b) A purely functional language lacks the ``go to'' statement, but an imperative language always has such a command. (c) All subprograms must be declared with the keyword function in a purely functional language. (d) There is no real difference, only a difference in the recommended coding style. ANSWER: A1.5 Attribute grammars are typically used to… (a) Handle left-recursion. (b) Handle language features which context-free grammars can not. (c) Prove program correctness. (d) Compile grammars into efficient tables. ANSWER: B 2. Finite state machines and regular expressions (20) Answer the following questions about the Finite State Machine or FSM (also known as a Deterministic Finite Automaton or DFA) depicted to the right. 2.1 Does this FSM have an initial state and if so which one – left or right? (2) YES, LEFT 2.2 Does this FSM have an accepting state and if so which one – left or right? (2) YES, RIGHT 2.3 Describe in a sentence or two the language that it defines. (5) The language of strings of 0s and 1s that contain an odd number of 1s. 2.4 Give a regular expression that defines the same language. Use the following notation for operators: + for one or more repetitions, * for zero or more repetitions, ? for optional expressions, | to separate alternatives. Parentheses can be used for scope. (5) : 0*10*(0*10*10*)* 2.5 Does every FSM have a regular expression that defines the same language? (2) YES 2.6 Does every regular expression have a FSM that defines the same language? (2) YES 2.7 Is it possible for a FSM to define an infinite language? (2) YES 3. Context free grammars (20) Consider the following context free grammar written using a BNF notation. S ::= a B S ::= b A B A ::= a A ::= A A b B ::= b B ::= b S B ::= a B B 3.1 Which symbols are the non-terminal symbols? (2) S, A , B 3.2 Which symbols are the terminal symbols? (2) a, b 3.3 Is the grammar non-recursive, left-recursive, right-recursive, of both left-and-right recursive? (2) both 3.4 Draw a parse tree for the string baababb (14) 4. Java true/false questions. (25) Mark each assertion as true or false by circling [T] or [F]. 00 1 1[T] or [F] : The constructor of a class must not have a return type. [T] [T] or [F] : A class that is abstract may not be instantiated. [T] [T] or [F] : The value of a static Java variable cannot be changed once it has been initialized. [F] [T] or [F] : A static variable indicates there is only one copy of that variable. [T] [T] or [F] : A method defined as private indicates that it’s accessible to all classes in the same package. [F] [T] or [F] : For each try block there must be at least one catch block defined. [F] [T] or [F] : A try block may be followed by any number of finally blocks. [F] [T] or [F] : A try block must be followed by at least one finally or catch block. [T] [T] or [F] : If both catch and finally blocks are defined, catch block must precede the finally block. [T] [T] or [F] : Arrays in Java are essentially objects. [T] [T] or [F] : It’s not possible to assign one array to another. Individual elements of array can however be assigned. [F] [T] or [F] : Array elements are indexed from 1 to size of array. [F] [T] or [F] : If a method tries to access an array element beyond its range, a compile warning is generated. [F] [T] or [F] : Each Java file must have exactly one package statement to specify where the class is stored. [F] [T] or [F] : If a Java file has both import and package statements, the import must precede the package. [F] [T] or [F] : A Java file must have at least one class definition. [F] [T] or [F] : If a Java file has a package statement, it must be the first statement except for possible comments. [T] [T] or [F] : The Java Virtual Machine compiles Java byte code into machine language instructions. [F] [T] or [F] : Java does not have true multiple inheritance like C++. [T] [T] or [F] : Java applets, but not Java applications, are run in a “sandbox” that limits