Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 3026 Computer Science

Sample Examination

[Part 1: Short Answer Questions  50 Marks]

1.  [5 marks] Evaluate the truth values of the given propositions. You must write not only the truth values, but also show how you derived your answer.

(a)  Based on the facts about the COMP 3026 Computer Science course, decide the truth values of proposition p, q, and r as described below.

p: The course has a one-hour lecture every week.

q: The workshop activities are part of continuous assessment.

r: The practical activities are using C programming language.

(b)  Based on the truth values from (a), evaluate the truth value of the following compound

proposition:           (!p || q) → !r

2.  [5 marks] Given the following diagram representing a function f from domain U to codomain A, answer each question below. You must also show how you derived your answer. (a)  Define a set B which makes A B the range of the functionf.

(b)  Find two subsets of U that will make f to become a one-to-one function and contains 4 elements.

3.  [6 marks] Given relations R and S on the set X = { a, b, c, d, e } are defined as below, for each relation, explain whether it is an equivalence relation and/or a partial order.

(a)  R = { (a,a), (a,b), (b,b), (b,a), (c,c), (c,d), (d,d), (e,e) }

(b)  S = { (a,a), (b,b), (b,c), (b,d), (c,c), (c,b), (c,d), (d,d), (d,b), (d,c), (e,e)  }

4.  [4 marks] Given a set of positional vectors P =  \$% 2( , % 2( , % 2(2)( , %  (+2(3) answer the following

(a)  What is the area of the convex hull formed by P ?

(b)  What is the area of the convex hull formed after applying a linear transformation defined by a matrix A  = %1(1)    2(0)( to each positional vector in P?

5.  [5 marks] Given the following finite automaton, show if the strings described in (a)-(c) are accepted or not by showing the simulated path (sequence of the state transitions). (a)  101101

(b)  A string based your last name by replacing each letter with 1 if it is a vowel (a e i o u), or with 0 otherwise.

6.  [5 marks] Given the following finite automaton, answer the following questions and show how you derived your answer. (a)  Find CL(E).

(b)  Create a string based on the number part ofyour university username (student email ID) by replacing each digit with 1 if it is an odd number, or with 0 if it is an even number. Show if the constructed string is accepted by the above finite automaton. If accepted show the possible sequence of transitions to the final state. If not accepted list the possible end states after processing the whole string.

7.  [4 marks] Considering the following regular expression E, what are the two shortest strings in L(E)?

1( 1+0)*01*+ 1*

8.  [4 marks] Consider the following context free grammar:

S  AB

A → 0A1 | 2

B → 1B | 3A

Assuming S as the initial symbol, apply rightmost derivations to generate a string: 021132

9.  [6 marks] Consider a Pushdown Automata with states Q = { q, f }, alphabet Σ={0, 1}, stack symbol alphabet Γ={X, Y, Z}, and transition function defined as the following table:

 State-Symbol 0 1 q - Z {(f, Z)} {(q, YZ)} q - Y {(q, ε)} {(q, YY)} - Z {(f, XZ)} {(q, Z)} - X {(f, XX)} {(f, ε)}

Given f  is  the  final  (accept)  state,  show  a  sequence  of moves  ( ⊢)  using  Instantaneous Description starting from (q, w, Z), and decide if w is accepted, where w is a string constructed based on the last 4 digits of your student ID number, and replacing odd number digit with 1, and even number digit with 0 (e.g., if the last four digits of your student ID are 5678, w = 1010).

10.  [6 marks] Consider a Turing Machine with a start state of q, input symbols of {0, 1}, a blank symbol of B, and transition function defined as the following table:

 0 1 B q (q, 1, R) (p, 1, R) (f, B, R) p (r, 0, L) (r, 1, L) (r, B, L) r - (q, 0, R) - f - - -

Simulate the moves of this Turing Machine ( ⊢) until it halts using Instantaneous Descriptions with an input string w which is formulated based on the last three numbers of your student ID, and replacing odd number digit with 1, and even number digit with 0 (e.g., if your student ID is 1234587, w = 101).

[Part 2: Long Answer Questions  50 Marks]

11.  [10 marks] Consider the sets,

X = { 1, 2, 3, 4}

Y = {2, 4, 6, 8, 10}

R = { (1,1), (1,3), (2,2), (2,4), (3,3), (4,2) }

(a)  Explain why a function from X to Y is always not invertible. (5 marks)

(b)  Define a set S which makes R S an equivalence relation and |S| = 2. (5 marks)

12.  [15 marks] Consider the following argument:

If it is past 12pm, I have lunch.

If I do not feel hungry, I do not have lunch.

Therefore, if I have lunch, I feel hungry.

(a)  Formulate propositional logic expressions (i.e., compound propositions) of the above argument. (5 marks)

(b)  Using a truth table, decide and explain if the above argument is valid or not. (5 marks)

(c)  Without using the truth table, explain why the above argument is valid or not by using contrapositive relation between compound propositions. (5 marks)

13.  [25 marks] Consider the finite automata with alphabet Σ={a, b, c} in the following graph: Create a transition table of this finite automata (5 marks). Convert it into a minimum-state DFA represented in a transition table, taking the steps ofremoving ε-transitions (5 marks), converting into a DFA (5 marks), then minimising the number of states (10 marks). You must write not only the final answer, but also explain how you derived your answer in your own word.