Egypt-Japan University of Science and Technology (E-JUST)

CSE 426 Theory of Computation

Assignment 1

Mark Eskander
University ID: 120210018
Email: [Link]@[Link]

February 25, 2025

Assignment 1 1

Sheet 2

Question 1.1
a
M1 = q1 M2 = q1

b
M1 = {q2} M2 = {q1,q4}

c
M1 = q1,q2,q3,q1,q1 M2 = q1,q1,q1,q2,q4

d
M1 =no M2 = Yes

e
M1 =no M2 = Yes

Question 1.2
For M1 : M1 = (Q, Σ, δ, q1 , F ) where:

• Q = {q1 , q2 , q3 } (set of states)

• Σ = {a, b} (input alphabet)

• q1 is the initial state

• F = {q2 } (set of final/accepting states)

• δ (transition function) is defined as follows:

δ(q1 , a) = q2
δ(q1 , b) = q1
δ(q2 , a) = q3
δ(q2 , b) = q3
δ(q3 , a) = q2
δ(q3 , b) = q1

For M2 : M2 = (Q, Σ, δ, q1 , F ) where:

• Q = {q1 , q2 , q3 , q4 } (set of states)

Mark Eskander - 120210018

Assignment 1 2

• Σ = {a, b} (input alphabet)

• q1 is the initial state

• F = {q4 } (set of final/accepting states)

• δ (transition function) is defined as follows:

δ(q1 , a) = q1
δ(q1 , b) = q3
δ(q2 , b) = q4
δ(q3 , a) = q2
δ(q4 , a) = q4
δ(q4 , b) = q4

Question 1.3
u d
d d d d
q1 q2 q3 q4 q5
u u u u

Question 1.4
a
b b b a,b

q0 a q1 a q2 a q3
start

p0 b p1 b p2
start

a a a,b

Mark Eskander - 120210018

Assignment 1 3

b
b b b a,b

q0 a q1 a q2 a q3
start

p0 b p1 b p2
start

a a a,b

c
b b

q0 a q1
start a

p0 b p1 b p2 b p3
start

a a a a,b

d
b b

q0 a q1
start a

p0 a p1
start
b

Mark Eskander - 120210018

Assignment 1 4

e
b a,b

q0 a q1
start

p0 b p1 b p2
start

a a a,b

f
b b

q0 a q1
start a

p0 b p1
start
a
b

g
a,b
start q0 q1
a,b

p0 a p1
start a

b b

Mark Eskander - 120210018

Assignment 1 5

Question 1.5
a
b a a,b

q0 a q1 b q2
start

b
a b a b a,b

q0 b q1 a q2 b q3 a q4
start

c
a a a,b

q0 a q1 b q2
start
b

q3 a q4

b a,b

d
a b

q0 b q1
start

e
b

q0 a q1 b q2
start
a

Mark Eskander - 120210018

Assignment 1 6

f
a,b

start q0

g
b b b a,b

q0 a q1 a q2 a q3
start

h
a,b

start q0

1 Question 1.6
a
1 0,1

q0 1 q1 0 q2
start

b
0 0 0 0,1

q0 1 q1 1 q2 1 q3
start

c
1 0 1 0 0,1

q0 0 q1 1 q2 0 q3 1 q4
start

Mark Eskander - 120210018

Assignment 1 7

d
0,1

0,1 0,1 0
start q0 q1 q2 q3

e
0 0,1
start q0 q1 q2
1 0,1

0,1
q3 q4
0,1

f
0 0 1 0,1

q0 1 q1 1 q2 0 q3
start

g
0,1

0,1 0,1 0,1 0,1 0,1 0,1

start q0 q1 q2 q3 q4 q5 q6

h
0 0 0 0,1

q0 1 q1 1 q2 1 q3
start

i
0

q0 1 q1
start
0,1

Mark Eskander - 120210018

Assignment 1 8

j
0 0,1

q0 0 q1 01 q12 1 q3
start

k
1 0,1

0 0,1
start q0 q1 q2

l
1 0 0,1

q0 0 q11 q2 1 q3
start
0

m
0,1

start q0

n
0,1

0,1
start q0 q1

Mark Eskander - 120210018