1 of 8Computer Science and Applied MathematicsV1May 11, 1998cs330 - Discrete StructuresSpring 1998Final Examclosed books, closed notesStarts: 10:30 am Ends: 12:30 pmName: (please print)ID: What happens with this paper (mark one): Discard Mail at this address: Problem Max points Your mark Comments1 102 103 104 105 106 10 10*17 10 5+58 109 10 5+510 1011 40 8*51402 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV11. Let f be the function that associates each person on Earth his/her height (expressed as aninteger number of inches). Decide whether f is bijective or not. 2. Consider the set of all regular expressions over the alphabet A={0, 1}. Decide whether thisset is countable or not. Prove your answer (a correct guess earns you 1/3 of the credit forthis problem). 3. Decide whether the following argumentation is valid or not. “The Discrete Structures classis fun or is boring. If Discrete Structures is fun then students learn. Therefore, if Discrete3 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV1Structures is boring students do not learn.” 4. Give an inductive definition for the set of all simple lists over the alphabet A={a, b} withthe property that the first and the last element in each list are the same. 5. Find a regular expression for the language consisting of strings that represent numbers inscientific normal notation. For the exponent you will use a caret (^). For example, insteadof 102 you would use 10^2.4 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV16. Determine whether the strings in the table belong to any of the languages described by thefollowing regular expressions: 7. Assume a FA described by the following state transition table: a) Draw the state transition diagram for this FA RE 1001 belongs to the language (T/F) 110 belongs to the language (T/F)10*1*(10)*+(1)*(00)*1*(01)*1(00)*1*(01)*10*(10 + 1)*InputState 0 1→ * s0s0s1s1s3s4* s2s2s4s3s3s3s4s3s25 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV1b) Decide which of the following strings are accepted by this FA 8. Construct a finite-state machine that takes an input string consisting of 0’s and 1’s and out-puts 1 when the last two characters read are different, and 0 otherwise. Use the Mealymodel. 9. G is a context free grammar defined by:N = {S, A} T = {0, 1} Start symbol: SProductions:S → 0S (1)S → 1 A (2)S → 1 (3)S → λ (4)A →1A (5)String Accepted (T/F)00110011000011000ε6 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV1A →1 (6)a) what is the language of G? b) find a leftmost derivation of the string 00111. At each step show the production used. 10. Find the binary single-precision representation for 9.375 11. Give a definition for:a) Set partition7 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV1b) Symmetric relation c) Connected graph d) Binary tree e) The inverse of a function f) The grammar of a language8 of 8Discrete Structures  Virgil Bistriceanu, 1997Spring 1998, Final ExamV1g) Regular Language h) A string being accepted by a