MAT2ALC: Algebra, Linear Codes and Automata Assignment 4, 2018 Due: Monday, 1 October, 10AM. Each page of your solutions must carry your name and your student number. Scan your assignment, and submit it as a single pdf file through the LMS. The printers around campus can be used to scan your assignment pages, and they can send a pdf of the scans to your student email. There are also smart phone apps that you can use to scan your assignment. Submissions that are not single pdf files will not be marked. By submitting your work electronically, you are affirming that it is all your own work, and you will be asked to confirm this as you submit it. Your assignment will be marked by your Monday practice class demonstrator. If you need an extension, you must arrange it with your Monday demonstrator before the due time. The names and emails of the demonstrators for each practice class are listed on the LMS. Questions Q 1. (a) Calculate the subgroup H := h(1 2 3)i of (A4; ◦). Write the elements in cycle notation. (b) Find the set of all left cosets of H in A4. [See PC7A, Q4 for a list of the elements of A4.] Q 2. Given that |U22| = 10, determine the order of 7 in the group (U22; ⊗22) by performing only three multiplications in (U22; ⊗22). Explain your reasoning. Q 3. Calculate 13257 in the group (U17; ⊗17). Q 4. Let G be the group of symmetries (including flips) of the regular heptagon (7-gon) shown at right. As usual, we regard the elements of G as permutations of the set of vertex labels; thus, G 6 S7. (a) Let σ denote the rotation of the 7-gon that takes the vertex 1 to the vertex 2. Write down the cyclic subgroup R := hσi as a set of elements of S7 in cycle notation. (b) What are the orders of each of the elements of R? (c) Write down any symmetry µ ∈ G\R in cycle notation. 7 1 2 3 4 5 6 (d) Find the left coset µR for your chosen µ from (c). What are the orders of each of the elements of µR? (e) According to Lagrange’s Theorem, what are the possible values of |H|, where H 6 G? (f) Let H be any subgroup of G other than G itself. Using (e), explain why H is cyclic. (g) Determine the number of subgroups of G (including G). Explain your answer. Q 5. Consider the subgroups G := h8i and H := h4i of U9. [See Assignment 3.] (a) Draw up the group table for G × H. [Hint: First write down the sets G, H, and G × H.] (b) Find an isomorphism ϕ: Z6 → G × H. [Hint: Show that O (8, 4) = 6 in G × H.] Q 6. From Assignment 2, we know that (Z; ∗) is a group, where x ∗ y := x − 3 + y for all x, y ∈ Z. Let ϕ: Z → Z be defined by ϕ(x):= x + 3 for all x ∈ Z. Show that ϕ is an isomorphism from (Z; +) to (Z; ∗). To show that ϕ is invertible, it is enough to write down the inverse function. Q 7. Optional Question (1 Bonus Mark). Find a permutation σ ∈ S7 such that hσi 6 S7 has exactly 420 distinct left cosets in S7. Explain carefully why your chosen σ has the required property Q 8. Let P be the following PDA with input alphabet Σ = {0, 1} and stack alphabet Γ = {1, }. q0 q1 q2 0, ε 7→ ε 1, 1 7→ ε ε, ε 7→ 11 0, ε 7→ 0 1, 7→ (a) Show how P processes the following words, indicating whether they are accepted or rejected. Assume that P always transitions from q0 to q1 in the first step of the computation (for this particular PDA, this ensures that there is a unique way to process a given input). (i) 1011 (ii) 00110 (iii) 101101 (iv) 110100 (b) What is the shortest word in Σ∗ accepted by P? Show that your chosen word is accepted. (c) Is the language L(P) accepted by P a regular language? If so, give a regular expression. If not, explain why not. Q 9. Consider the context-free grammar G with terminal symbols T = {x, y, e, −1 ,(,)}, non-terminal symbols N = {σ, F, B}, starting symbol σ, and production rules σ → F σ F F → B B −1 B → x y e (F σ) Note that we are regarding −1 as a single symbol. The string B−1 , for example, has length 2; it is the symbol B followed by the symbol −1 . (a) Give leftmost derivations in G for each of the following strings. (i) ee (ii) (xy) −1 (iii) yxy−1 (iv) x(ex) −1 (b) Use the method of Lecture 8B to draw the transition diagram of a PDA accepting the language generated by G. State the input alphabet and the stack alphabet of your PDA. (c) Show how your PDA in (b) accepts the string (xy) −1 . Your answer to (a)(ii) will be useful. Q 10. Optional Question (2 Bonus Marks). Design a PDA accepting 0 2n1 n | n ∈ N0 . You should specify your PDA with a transition diagram, and also clearly state your chosen stack alphabet. The following question is a proof question. It will be worth 3% of your final mark, so you are strongly advised to attempt it. Q 11. Proof Question. Let G and H be groups, let ϕ: G → H be an isomorphism, and let ψ be the inverse function of ϕ. Prove that ψ is an isomorphism from H to G. This assignment will be worth 8% of your final mark. Your assignment is marked out of 24, according to the breakdown shown in the table. Not every question is marked; you should self-assess the unmarked questions. You will get 2 completeness marks for making a serious attempt at all questions. The 3 written communication marks are based on your usage of English and mathematical grammar for the non-proof questions. The 9 marks for the proof question will include marks for written communication as well. Mathematics 10 marks Completeness 2 marks Written communication 3 marks Proof question 9 marks Total 24 marks