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 PowCoder代写 加微信 powcoder
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. aba→b 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. aba→b
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. #b→b#
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com