[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;
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. abab 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. abab 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: assignmentchef QQ: 1823890830 Email: [email protected]