Instructions:

1. Do not change the problem statements we are giving you. Simply add your solutions by editing this latex document. To make it easier for the TAs to find your solutions, please use the soln environment we provided as follows:

\begin{soln}

My  solution  is here.

\end{soln}

Your solution will then appear in blue, and be easier to differentiate from the questions.

2. If you need more space,  add a page between the existing pages using the  \newpage command.

3. Export the completed assignment as a PDF file for upload to gradescope.

4. On Gradescope, upload only one copy per partnership. You must identify all member of your group via Gradescope, not doing so may result in loosing some marks.

5. You must also tell us, via Gradescope, where each of the problem parts appears on your submission.  You must align the regions for every problem, even if your assignment solution isn’t complete.  We will not be able to mark any problem we can’t find.  After uploading the .pdf you will a screen, where you can click each question on the left, and click the corresponding page(s) for which the question appears in.  This video has detailed information about how to submit assignments on Gradescope.

6. Please allocate at least 5 minutes prior to the deadline for the matching process.  You must match your answers with each question, not doing so may result in loosing some marks.

Academic Conduct: I certify that my assignment follows the academic conduct rules for of CPSC 121 as outlined on the course website. As part of those rules, when collaborating with anyone outside my group, (1) I and my collaborators took no record but names away, and (2) after a suitable break, my group created the assignment I am submitting without help from anyone other than the course staff.

1. [6 marks] Given the following definitions:

• S: the domain of all CPSC 121 students.

• M: the domain of all items on the all-you-can-eat sushi menu.

• E(x,y): student x eats menu item y

• L(x): student x receives a "Like" on Instagram.

We investigate how parenthesization can affect the meaning of predicate logic statements. Consider the predicate logic statements below:

Statement 01: ∀x ∈ S,∀m ∈ M,E(x,m)↔ L(x)

Statement 02: ∀x ∈ S,(∀m ∈ M,E(x,m))↔ L(x)

Statement 03: ∀x ∈ S,(∀m ∈ M,(∀y ∈ S,E(y,m)))↔ L(x)

Describe how these statements differ, in terms of who receives a "Like" and under what conditions.

2. [12 marks] An integer x is called prime if the only two positive integers that evenly divide it are 1 and x.

Using these definitions, rewrite each of the following theorems using quantifiers and pred- icates.  You do not need to prove these theorems; you only need to express them using predicate logic. Note that the theorems are not precisely stated.

You are allowed to use only the predicate Prime(x) that is True if x is a prime, and False otherwise.  No other predicates can be used. You can also use either | or the mod definition to indicate that a number is divisible by another.  Consider all numbers as positive integers.

a. [4 marks] Mersenne primes: Every prime number of the form 2p  − 1 has a prime number p as its exponent.

b. [4 marks] Sum of three cubes: Every integer from 1 to 113 can be expressed as the sum of three perfect cubes.

c. [4 marks] Mihăilescu’s theorem: There are no two powers of natural numbers besides

23  and 32  whose values are consecutive.

3. [8 marks] Construct a regular expression that accepts only strings specified by each set description. To aid with grading, include a detailed explanation of the components of your regular expression.

a. [4 marks] Real numbers in the range of [ −32, 56]. Leading zeros will not be accepted, but trailing zeros will be accepted. For simplicity, also allow negative zero.

b. [4 marks] File name strings in Pascal case (first letter of each word is capitalized, with no spaces), followed by a dash, followed by a 3-digit number (leading zeros OK), followed by the extension ".jpg" or ".png".  Do not worry about whether character

strings form actual dictionary words.

Examples of accepted strings:

• MyLimitedEditionMountainDewCollection-002.jpg

• BlahbLahblAhZkjenDlke-664.png

• AAAAAaaahhh-555.jpg

Non-accepted strings:

• Bacon.Double Cheeseburger-100.jpg

• notPascalCaseAndNoNumber.gif

4. [6 marks] Design a DFA that accepts only strings over the alphabet [A − Z] containing the following features:

• Contains at least two ’R’s

• Does not contain both ’P’ and ’T’

• Any occurrence of ’S’ must have an ’E’ somewhere (but no necessarily immediately) after it

Examples of accepted strings:

• CORVISQUIRE

• PERRSERKER

• STONJOURNER

Examples of rejected strings:

• PINCURCHIN (does not contain at least two Rs)

• SPECTRIER (contains both P and T)

• GRIMMSNARL (E does not appear somewhere after S)

Hint: If you want, you can use https:// www.madebyevan.com/fsm/ to draw your DFA.