[SOLVED] CS Theoretical Computer Science (M21276)

Theoretical Computer Science (M21276)
Part B/1: Computability and Equivalent Models, Part 1
(Nov 29-Dec 3, 2021)
Model 2: A simple programming language

Copyright By Assignmentchef assignmentchef

Question 1. Using a simple programming language write a simple code for the following
macros (you can use the macros which we have defined before X := Y ):
1. X := 4;
Answer: X := 0; X := succ(X); X := succ(X); X := succ(X); X := succ(X);
2. X := X + Y ; Answer:
while I = 0 do
X := succ(X); I := pred(I) od
3. repeat S until X = 0;
Answer: S;whileX=0doSod
4. loop forever
5. Z := X + Y ; Answer:
6. ifX=0thenSfi
X := 0; X := succ(X); while X = 0 do S od
while Y = 0 do Z:=succ(Z);Y :=pred(Y); od

7. ifX=0thenSelseT fi; Answer:
Temp := X;
while Temp = 0 do
S; Temp:=0; od
A := X;B := 0;B = succ(B)
while A = 0 do S;A := 0;B := 0 od; while B = 0 do T;B := 0 od.
Model 3: Markov algorithms
Question 2. Describe the form of the output of the following Markov algorithm over
{a,b} for an input string of the form aibaj. 1. ba b
2. abab 3. b
Answer: ai
Question 3. Describe the form of the output of the following Markov algorithm over
{a, b} for an input string of the form aibaj (j i). 1. abab
2. b 3. ba b
Answer: aj i
Question 4. Find a Markov algorithm to replace each a with aa in strings over {a, b}.
Answer: 1. #a aa# 2. #bb#
3. # (halt)

Question 5. You are given the Markov algorithm over {0, 1} with the following set of production rules:
1. |0 0|| 2. 1 0| 3. 0
Find out, what the algorithm calculates. Start by exploring the strings 101, 1, 111, . . . Answer: rewrite binary numbers to their unary counterparts
Model 4: Post algorithms
Question 6. You are given the following deterministic Post algorithm which modifies the strings over the alphabet {a, b, c}. Figure out how the algorithm modifies the input string aacbacb. Can you formulate the problem which the given Post algorithm solves?
aX @b#X bX @b#X cX @c#X
@X#aY @Xb#Y @X#bY @Xb#Y @X#cY @Xc#Y
@X# X (halt) bbcbbcb, replace all occurences of a by b
Question 7. Find another Post algorithm (can also be non-deterministic) which modifies the strings over the alphabet {a,b,c} in the following way: replace all occurrences of a by b.
Answer: XaY XbY

CS: assignmentchef QQ: 1823890830 Email: [email protected]