Call Now: (800) 537-1660
 Home    Why?     Free Solver   Testimonials    FAQs    Product    Contact

May 22nd

May 22nd

# Discrete Structures Final Exam

 Problem Max points Max points Comments 1 10 2 10 3 10 4 10 5 10 6 10 10*1 7 10 5+5 8 10 9 10 5+5 10 10 11 40 8*5 140

What happens with this paper (mark one): DiscardMail at this address :

1. Let f be the function that associates each person on Earth his/her height (ex pressed as an
integer
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 this
set is countable or not. Prove your answer (a correct guess earns you 1/3 of the credit for
this problem).

3. Decide whether the fol lowing argumentation is valid or not. “The Discrete Structures class
is fun or is boring. If Discrete Structures is fun then students learn. Therefore, if Discrete
Structures is boring students do not learn.”

4. Give an inductive definition for the set of all simple lists over the alphabet A={a, b} with
the 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 in
scientific normal notation. For the exp onent you will use a caret (^). For example, instead
of 102 you would use 10^2.

6. De termine whether the strings in the table belong to any of the languages described by the
following regular expressions:

 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)*1 (00)*1*(01)*1

7. As sume a FA described by the following state transition table:

a) Draw the state transition diagram for this FA

b) Decide which of the following strings are accepted by this FA

 String Accepted (T/F) 00110 011 0000 11000 ε

8. Construct a finite-state machine that takes an input string consisting of 0’s and 1’s and outputs
1 when the last two characters read are different , and 0 otherwise. Use the Mealy
model.

9. G is a context free grammar defined by:
N = {S, A} T = {0, 1} Start symbol : S
Productions:

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 partition

b) Symmetric relation

c) Connected graph

d) Binary tree

e) The inverse of a function

f) The grammar of a language

g) Regular Language

h) A string being accepted by a DFA

 Prev Next

Home    Why Algebra Buster?    Guarantee    Testimonials    Ordering    FAQ    About Us
What's new?    Resources    Animated demo    Algebra lessons    Bibliography of     textbooks