MAT2ALC Assignment 3: Solutions for Algebra, Linear Codes and Automata

This document provides a comprehensive solution to the MAT2ALC Assignment 3, focusing on topics covered in Weeks 5 and 6 of the course. The assignment includes problems related to group theory, specifically exploring the properties of U14 and its subgroups, as well as the symmetries of a regular octagon. Solutions involve calculating the order of elements, determining cyclic groups, and analyzing subgroups. The assignment also delves into automata theory, covering the Suffix Equivalence Algorithm, the conversion between grammars and NFAs, and DFA simplification. The solutions provide detailed steps, including calculations, diagrams, and derivations, to help students understand and solve problems related to algebra, linear codes, and automata.

Running head: MAT2ALC 1
MAT2ALC (Algebra, Linear Codes and Automata)
Name
Institution

MAT2ALC 2
Q1
(a) Write down the set U14.
Solution
U (14) = {1, 3, 5, 9, 11, 13}
(b) Find the order of each element of U14 in the group (U14; ⊗14). Give the details of your
calculations, but try to do as few calculations as you can, instead justifying your answers
using Chapter 6. You may find it convenient to give your final answer in table form.
Solution
Orders of elements for U (14) are as follows;
| 1 | = 1
| 5 | = 6
Therefore, 51 =5 ≠ 1
52 =25≡1411 ≠1
53 ≡1413 ≠ 1
54 ≡149≠ 1
55 ≡143 ≠ 1
56 ≡ 1415 ≡ 141
Similarly, | 3 | = 6
| 9 |= 3 as 91 = 9 ≠1
92 = 81 ≠ 1411 ≠ 1
93 ≡ 1499 ≡ 141
(c) Is (U14; ⊗14) a cyclic group? Justify your answer.
Solution
Yes, it is cyclic since | U (14) | = 6
, and | 5 | = | 3 | = 6,
Therefore,
< 5 > = < 3 > = U (14)
(d) Write down all subgroups of (U14; ⊗14), and explain why there are no subgroups other
than these. You may use any of the results from Chapter 6 in your explanation.
Solution
| U (14) = 6 we apply the theorem for a cyclic subgroup of order n, a unique subgroupⱻ
of orders m, where m is a divisor of n.
As | u (14) | = 6 by cyclic theorem, all subgroups and only subgroups are {1}, < 13>, < 9
>, < 5>

MAT2ALC 3
Q2. Let G be the group of symmetries (including flips) of the regular octagon (8-gon) shown on
the right. As usual, we regard the elements of G as permutations of the set of vertex labels; thus,
G ≤ S8
.
a. Calculate the order of G using the Stabiliser-Orbit Theorem.
Given, G is the group of symmetries of the polygon (A)
(A)
b. Let μ denote the flipping symmetry of the 8-gon that takes the vertex 1 to the vertex 6.
Write the permutation μ in cycle form (as a cycle or a product of disjoint cycles).
Solution
Let μ be the permutation that takes vertex 1 to vertex 6, and also be the rotation matrix,
then,
μ =
c. What is the order of μ in the group G?

MAT2ALC 4
μ=
μ2=
μ2.μ2= μ8 =
μ2.μ8 = μ6
μ6.μ=μ8=
This implies that | μ | = 8
d. Does μ stabilise any vertex?
Solution
μ133 = μr
Claim find smallest such that r
μf μ133 = (μ8)13
= (μ8)19
, therefore, μ8 = identity permutation
(μ8)19= μ133= μ8=

MAT2ALC 5
, thus, μ133 = μ8
, hence, r = 8 is the smallest such r.
e. Find the smallest non-negative integer r such that μ 133 = μ r, and hence calculate μ 133.
Solution
< μ > {μ, μ2, μ3, … μn }, in part c above, we know that μ8 = I, I identity
Now if the value of n in set < μ > is greater than 8, then by division algorithm, b, c > 0ⱻ
set n = 8b + c, where 0< c < 8
μn = μ8b + c = (μ8) b. μc
= μc { μ8 = I}, thus powers of μ in the set < μ > cannot be greater than 8, since |
μ| = 8 , μi are distinct for I = 1, 2, 3, …8.
|< μ >|= 8
f. Determine the order of the cyclic subgroup (μ) of G. Justify your answer.
Take μ=
, and α =
Now, μα =

MAT2ALC 6
, and αμ=
This implies that μα ≠ αμ,
G is non-Abelian
g. Show that G is non-Abelian.
From e above μα ≠ αμ and hence G cannot be cyclic since every cyclic group is abelian.
h. Is G a cyclic group? Justify your answer.
Solution
Take α = (2, 8) (8, 5)
α .α= ((2, 8) (8,5) (2, 8) (8, 5) ) = I
α2 = I
, thus, H = { T, α } is a subgroup, ( since I.α = α, α.α= I, therefore, if H is closed under
group operation) and |H|= 2.
Q3. By the Latin Square Theorem, any group table for a finite group forms a Latin square. The
converse is false. In fact, a binary operation can have a Latin square table, an identity element
and two-sided inverses, and yet fail to be a group operation. Prove this by showing that the table
on the right is not a group table.
. 0 1 2 3 4 5 6
0
1
2
3
4
5
6
0 1 2 3 4 5 6
1 2 0 5 6 4 3
2 0 1 6 5 3 4
3 6 5 4 0 1 2
4 5 6 0 3 2 1
5 3 4 2 1 6 0
6 4 3 1 2 0 5
Solution
If G. [0 1 2 3 4 5 6], every element for the group must show up exactly once in each row and
column; no element can show up twice in any row or column. Assuming that x show up twice in
a row, then X: a x b, X: a x c, X: a x d, X: a x e, X: a x f, X: a x g for some value a=0, b=1, c= 2,
d= 3, e= 4, f=5, g=6, that is a, b, c, d, e, f, g, G.
a’ (a x b) = ‘a (a x c) = a’ (a x d) = a‘(a x e) = a’ (a x f) = a’ (a x g)

MAT2ALC 7
This implies that;
(a x a) x b = (a x a) x c = (a x a) x d = (a x a) x e = (a x a) x f = (a x a) x g
So, b=c=d=e=f=g,
Thus every element appears at least once in every row and column, G is a group with n elements
corresponding to G [0 1 2 3 4 5 6]. It can be through if the mapping corresponds to their
performance.
Q4.
(a) Apply the Suffix Equivalence Algorithm to the complete DFA shown on the right. (Just
the table is required for the answer.)
Solution
0 1
A D B

MAT2ALC 8
B
C
D
E
C E
E B
D B
D B
(b) Hence, write down the partition induced by the suffix equivalence relation.
Solution
Step1: find ‘0’ equivalence
Separate find and non-find states
0-equivalence [A, C, D, E] [B]
Step2: Find ‘1’ equivalence
(i) (A,C) a (D,E)
(A, C) b (B,B) 1-equivalence [A, C, D, E] [B]
(ii) (C, D) a (E, D)
(C, D) b (B, B)
(iii) (D, E) a (D, D)
(D, E) b (B, B)
Step3: 1-equivalence equals 0-equivalence and the process stops there, A, C, D, E, are all
equivalent states
[A, C, D, E] [B]
0 1
[A, C, D, E]
B
[A, C, D, E] [B]
[A, C, D, E] [A,C,D,E]
(c) Draw the diagram of the simplified machine.
solution

MAT2ALC 9
Q5. Consider the regular grammar G with terminal symbols {0, 1}, non-terminal symbols {σ, A,
B, C}, starting symbol σ, and production rules σ → 0A | ε, A → 1A| 0B |1C, B → ε, C → 0B.
a. Convert the grammar G to an NFA over {0, 1}. (Just give the transition diagram.)
σ is the initial state and also the final state since ε should also be accepted. B is also a
final state. B -> ε just means that you are not accepting anything once you reach B. 0A
means that after seeing a 0 when in state σ, state A would be reached. The same applies
for other transitions.
b. Let N be the NFA from (a). Give an accepting computation (in N) of the string 01110.
Below is a representation of how the input string will be processed by the NFA;
c. Give the derivation of the string 01110 in G corresponding to the computation in (b).
The derivation by grammar G using the production rules will be as follows:
d. The partial DFA M shown on the right is equivalent to N. Convert M to a regular
grammar. Clearly identify the sets of terminal and non-terminal symbols, the starting
symbol, and the production rules.
Solution

MAT2ALC 10
S is the starting symbol. Since it is also the final state, ε would be accepted. From S on
seeing 0, state U is reached. From U on seeing 0, state V is reached. V is the final state
which does not process any non-terminal, therefore V -> ε
e. Let H be the regular grammar from (d). Derive the string 01110 in H
Solution