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