DMTH237 Discrete Mathematics

Macquarie University

Department of Mathematics & Statistics

DMTH237 Discrete Mathematics II S1 2019

Assignment 1

1. Calculate the following products of complex numbers.

1. (2 − 3i) × (1 + 5i)

2. (a) Express each of the following complex numbers in polar form.

1. i
2. √3 − 3i
3. √−3 − 3i

(b) For each of the complex numbers in part (a), find z² and z⁴² .

3. Calculate the first four powers of the complex number −1+i, and sketch the resulting numbers in the complex plane. What do you notice? What do you expect for (−1 + i)⁴³ = (−1 + i)⁴²⁺¹ ?

4. Solve the following (related) systems of linear equations by row reduction.

^⎧ x − 2y + z − 4w = 1 ^⎧ x − 2y + z − 4w = 1

⎪⎨ ⎪⎨

(a) 2x − 24y − 22z − 32w = 10 (b) 2x − 24y − 22z − 32w = −2

^⎪⎩2x + 6y + 14z + 4w = 4 ^⎪⎩2x + 6y + 14z + 4w = 4

Make sure to verify that any ‘solutions’ you find are indeed solutions of the given system of equations.

5. In this question, make sure that you follow the proper definition of the power .

Suppose that A = 1,2,3,4. Suppose further that L,M ⊆ A^∗ are given by

M = 2,12,13,42. Determine how many distinct strings there are in each of the following languages. Write them all down when finite in number.

M L (b) L²M (c) M² + L³

In each case, identify explicitly those strings that can be constructed in more than one way.

6. A file named txt can be downloaded from the ‘Assignments’ panel on the DMTH237 iLearn site. It contains 100 binary strings, each of length 100 characters.

For each of the regular expressions given below, find the line-numbers of

which match the given regular expression, perhaps in more than one way —stating so with a brief explanation, if that is the case.

You may use whatever software you choose to answer this question; e.g., it can be done using the Find panel of most text-processing software applications, though other specialised utilities may prove to be easier to use, but may first require you to learn how to adapt to the specific language employed to denote a regular expression.

You should describe briefly what software you have used, and how you have used it to determine the required line-numbers. Include a screenshot, or other graphic, to help the markers understand what you did to get your answers.

1. Find matches to: (0 + 1)^∗ 1111111111(0 + 1)^∗.
2. Find matches to: (0 + 1)^∗ (00000000 + 11111111)000(0 + 1)^∗.
3. Find matches to: (0 + 1)^∗ 000000(0 + 1)¹² 111111(0 + 1)^∗.

Here a numerical exponent (...)^k means “k consecutive matches to the ‘...’ ”.

7. Write down a Regular Expression for the language L consisting of all binary strings where every nonempty block of 0s has odd length and every non-empty block of 1s has even length.

(Notice that the empty string is in this language.)

8. Suppose that S = A,B,...,F is a set of states and I = O = 0,1 are the input and output alphabets for the Mealy machine described by the transition table below.

1. Construct a state diagram for this Mealy machine.

(Layout the states so that there is no need to have transition arrows crossing each other.)

2. Find the output string corresponding to the input string

‘0110010100101’, when starting in state A.

In which state does the machine finish?

3. Design a Moore machine which produces the same output as Ethe Mealy machine in the previous question. In removing any Finaccessible states, discuss which state or states are valid as the initial state; choosing that which keeps the total number of states to a minimum, if this is possible.