Discrete Maths Assignment | Problems

DISCRETE MATHS
Problem 1
Part A
ΦU(b(aa)*)= D[(φ +(b.a)*]
=Ui(D[φ +(b.a)*] i.e the ith Union of domain of null element and product of elements {a,b}
={ ∈}U{φ,ba}UD[(φ + (b.a))]2U………..
={ ∈,φ,φφ,ba,φba,bφa,bφbφ}U……
={ ∈,φ,φφ,ba,baφ,φφba,baφφ}
This is a regular expression hence an element of RE.
D-The domain function
∈-Elements within a domain
φ is a null element
PART B
abUbbUφ=D[(a.b)φ+(b.b)+φ*]
=Ui[D(a.b) +(b.b) +φ*]
=D[a.b]UD[b.b]+D[φ]
={∈}U{ab,bb}UD[a.b +b.b]2U..
={ ∈,φ,φb,ba,abφ,bφb,φab,bφb}U………..
={∈,abφ,bφb,}
={ab,bb} Hence not an empty vector .It is having strings with another case .Thus abUbbUφ ∈RE
Hence not an element of RE.
PART C
Given that R is a regular expression that denotes a formal language by means of a function D.
1)D[φ]={Ƹ}
For each of a ∈∑ ❑

2)D[a] ={a}
3)D[b] ={b}
Therefore;
D[a.b]={X∈D[a],y∈D[b]}
={x.y|x ∈{a},y∈(b)}
={a.b}={ab}
D[a+(a .b)]=D[a]UD[a.b]
={a}U{b}
={a,ab}
Where {Ƹ} is an empty element i.e void
U is the union of the domain or elements.
PART D
L((α Uβ))=D[α]UD[β]
={α} U{β}
={α,β}
L((α,β))=D[α.β]
={x.y|x∈D(α),y∈ D ¿β]}
={x.y|x∈{α},y∈{ β ¿ }
={α.β}
={αβ}
L(α*)=D[α*]={Ƹ,α,αα,ααα,……}
Problem 2
PART 1
A palindrome is a string that is read the same from left to right and from right to left.

First half of the palindrome is a mirror image of the second half.
For instance;
An empty string is a palindrome.
A string containing only a single character is a palindrome.
A string a,b,c is a palindrome ,if b is a palindrome and a is a character equal to c.
These may constitute;
a,b,aba,abba,babbab.
The Palindrome over summation:
i)S ∈ Pal i.e S which is an element of palindrome and palindrome a member of S.
ii)For any s ∈ ∑ ❑,S∈ pal i.e when s is an element of its summation ,s and its summation is also a
member of palindrome and palindrome a member of s and its summation.
iii)For any x which is an element of pal,and S an element of summation,then sxs ∈pal.
No strings in pal unless it can be obtained by the rules stated in (i,ii,iii)
But
To iterate through the rules for pal over summation;
={s,t}
-i=0 pal={^,s,t} i.e when I is 0,the elements are self-contained in s and t.
-i=1 pal ={^,a,b,aaa,aba,bab,,bbb,aaaaa,aabaa,abbba,baaab,ababa,bbabb,bbbbb}
PART 2
Let S be a set defined as :
16 ∈ S
If y ∈ S ,then y2 ∈ S
You can prove that for ∀x ∈ S ,x is even
Proof:
Let R be the proposition that we want to prove.

From the inductive base;
16 ∈ S.
16 is an even number hence ,P({16}) holds.
From the inductive hypotheses:
S builds set S’ from the previous versions of S.
Assume that ∋S’ is such that |S| ≥1 and P(S) i.e ∋S’ is S contained as a member of other elements such
that the magnitude of s ≥ 1
Inductive step:
You will prove that P(S’U{y2 |y∈ S}) holds
Let y0 be the element selected arbitrarily from S’.But you know that y0 is an even number.
From the theorem,y02 is also even.
Since y0 was arbitrarily selected from S’,P(S’U{y2|x∈S’) holds,P({x0}) holds to be even.
PART 3
Assume that all sets are positive even integers.
We can show that;
Pal ⊂ S
S ⊂ Pal
You need to prove that every even positive integers, belong to S.
Let P(n):=2 ∈S
If P(n) is true ,we can conclude that P(n+1)=2(n+1) =2n +2 ∈S
But
2n∈ S and 2∈ S
To prove that S ⊂ E ,show that any element in S is a multiple of 2.
From recursive definition of S ,if a ∈ S^ b∈ S,it implies that a +b ∈ S
Hence,

x∈ →x =a +b=(a1 + b1)=(a2 + b2 )=………
x=2 + 2 +……..+2
This indicates that 2 is a multiple of x .Thus S⊂ pal
Problem 3
The Prim’s Algorithm:
i)Identify a single vertex arbitrarily from the graph to initiate a tree.
ii)Expand the tree from an edge i.e edges that connect to other vertices which are not yet the tree and
find the minimum edge-weight.Tranfer this to the tree.
iii)Repeat step two until all vertices are obtained in the tree.
Starting from vertex G,
You can get a web network that includes:
G→H→ E→ C→ D→ A→ B→ F
Edges:GH +EC +DA + AB +BF
Cost =8 +4 +9 + 3 +7 +1 +10=42
Edges:
G→H→ D→ A→ B→ F
Cost=GH+HD +DA +AB +BF
=8 +11 +7 +1 +10=37
Edges: G→F→ B→ A→ D→ H
Cost=6+10 + 1 + 7 +11 =35
Edges: F→B→ A→ D→ C→ E→ H
Cost :6 +10 +1 + 7 + 3 +9 +4 =40
Edges: G→F→ B→ A→ D→ H
Cost=6+10 + 1 + 7 +11 =35

Is the minimum weigh spanning graph.
PART 2
-Create an algorithm of size V and initiate it with nill
-Create a minimum Heap of size V and let the minimum heap be R .
-Insert all vertices into R such that key values of starting vertex is 0 and key values of other vertices is
infinite.
While R is empty;
U=extractMin(R)
For any adjacent of u;if u is in Update the key values of u in R of the weights.
You will realize that G→0
When you update other vertices, they tend towards infinite.
PART 3
VERTEX KEY BOUNTS
G 0 NILL
H ∞ NILL
E ∞ NILL
C ∞ NILL
D ∞ NILL
A ∞ NILL
B ∞ NILL
F ∞ NILL
When Vertex T is added;
VERTEX KEY BOUNTS
G 0 X NILLX
H ∞(4) NILL
E ∞ NILL
C ∞ NILL
D ∞ NILL
A ∞ NILL
B ∞ NILL
F ∞ NILL
T ∞ Nill

More than two edges can be added to the minimum spanning tree. IN our cases, three edges should be
added from G to complete the network.
Starting from vertex T,
You can get a web network that includes:
T→G→H→ E→ C→ D→ A→ B→ F
Edges:GH +EC +DA + AB +BF
Cost =0+8 +4 +9 + 3 +7 +1 +10=42
Edges:
T→G→H→ D→ A→ B→ F
Cost=GH+HD +DA +AB +BF
=8 +11 +7 +1 +10=37
Edges: T→G→F→ B→ A→ D→ H
Cost=6+10 + 1 + 7 +11 =35
Edges: T→F→B→ A→ D→ C→ E→ H
Cost : 0+6 +10 +1 + 7 + 3 +9 +4 =40
Despite adding more vertex ,there is no any other better edge found.