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;
2. X := X + Y ;
3. repeat S until X = 0;
4. loop forever
5. Z := X + Y ;
6. ifX̸=0thenSfi
7. ifX̸=0thenSelseT fi;
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 → Λ
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
Question 4. Find a Markov algorithm to replace each a with aa in strings over {a, b}.
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, . . .
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)
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.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com