Recent posts in Theory of Computation

First let me define what is “Divisibility language”.

We have two very similar looking type of languages. I call one type “Length divisibility language” and other I call “Divisibility language” 

"Length divisibility machines/languages" are different from "divisibility languages".

Let me define what I mean by “Length divisibility language” and by “Divisibility language” :

Length divisibility language : Given binary string w, we ask questions like :

(length of w) mod n = r, Or

(#0 in w) mod n = r, Or

(#1 in w) mod n,

etc.

Divisibility language : Given binary string, we ask Question :

(Decimal value of that binary string) mod n = r

So first we should Note this difference between the two types of languages or problems. 

For Length divisibility, we have the result that minimal DFA will have n states(regardless of r), for Length divisibility by n problem. But for divisibility languages, this might not be true. Yes, we can say that for divisibility language, minimal DFA will have at most n states. 

Result 1 : For Length divisibility by n languages, as described above, the number of states in minimal DFA will be ALWAYS n. 

Result 2 : For divisibility language, binary string divisible by n, when r = 0

i.e. (Decimal value of that binary string) mod n = 0

we have the following results :

(a) : In binary numbers, if the divisor is a power of 2 (i.e. n = $2^k$) then the minimum number of states required will be $k+1$.

How would you design such an automaton? Just see the properties of binary numbers. For a number, say 8 (which is $2^3$), all its multiples will have the last 3 bits as 0. For example, 40 in binary is 101000. Therefore for a language to accept any number divisible by 8 we just need an automaton which sees if the last 3 bits are 0, which we can do in just 4 states instead of 8 states. (In fact, this can be extended to any base. For a ternary base number system, if for example we need to design an automaton for divisibility with 9, we just need to see if the last 2 numbers of the input are 0. Which can again be done in just 3 states.)

(b) : If the divisor isn't power of 2 :

In a binary system, for example, if we take the divisors of 3 then 3 states in mDFA, 

For any odd number n in a binary system, we need n states in minimal DFA to define the language which accepts all multiples of n.

On the other hand, if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.

For example, if we need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 20, we do :

20/2 = 10 

10/2 = 5

Hence our answer is 5 + 1 + 1 = 7. (The 1 + 1 because we divided the number 20 twice).

 Exercise Question : L = { $w | w \in \{ 0,1 \}^* , w \text{ is multiple of 6 and 8} $ }

Answer : Binary number divisible by 6 and 8, then we know that a number is divisbile by 6 and 8 if and only if it is divisible by 24 (LCM(6,8) = 24), so, finding the number of states in mDFA for the language "binary number divisible by 6 and 8" is same as finding the number of states in mDFA for the language "binary number divisible by 24".

Now, coming to finding the number of states in mDFA for the language "binary number divisible by 24", Note that 24 is neither an odd number, nor a power of 2, So, we apply the following procedure :

if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.

We need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 24, we do :

24/2 = 12 

12/2 = 6

6/2 = 3

Hence our answer is 3 + 1 + 1 + 1 = 6. (The 1 + 1 + 1 because we divided the number 24 thrice).

So, answer will be 6, Not 48 or 16. 

NOTE : Note that This divisibility language formulas assume that Empty string is divisible by n.

PROOF of ALL the above claims :

Refer the following brilliant post by Arjun sir for proof of few of the above claims.

https://gateoverflow.in/blog/8651/minimum-number-states-dfa-accepting-binary-number-divisible

I will prove here that :

For any odd number n in a binary system, we need n states in minimal DFA to define the language which accepts all multiples of n. 

Objective : To check a binary number for divisibility by any odd number k requires k states in the minimal DFA.

Note that any binary number $abcd = (ab)2^2 + cd; abc = (ab)2^1 + c$

In general, $a_na_{n-1}\dots a_1 = (a_na_{n-1 \dots a_{x+1}})2^x + (a_xa_{x-1} \dots a_1)$

Theorem 1 : If a divides pq and is relatively prime to p then it divides q.

http://www.math.ubc.ca/~cass/courses/m446-03/divisibility.pdf

Proof :

Statement : Language of binary numbers divisible by any odd number n requires n states in the minimal DFA.

The way to prove such results is to twofold: first we prove an upper bound by constructing a DFA accepting the given language(that is n), then we prove a lower bound using Myhill–Nerode theory.

Now I'll prove, by Myhill Nerode Theorem that if n is odd number then All the numbers from 0 to n-1 will be mutually distinguishable.

Note that 0 is already distinguishable from 1 to $n-1$. So, we only need to show that All the numbers from 1 to n-1 will be mutually distinguishable.

By Myhill nerode theorem, two strings u and v are distinguishable if and only if there is some string w such that exactly one of uw, vw belongs to our language. 

Take any string $u$ whose decimal value is $a ; 1 \leq a \leq n-1$ , We will add append some string $v$ to $u$ such that uv belongs to our language i.e. $decimal(uv)$ is multiple of $n$. Let $decimal(v) = m$ and let $|v| = i$

So, $a(2^i) + m = n(X)$ 

Now, take any $b; 1 \leq a < b \leq n-1$ different from $a$ i.e. $a \neq b$ 

 $m = n(X) - a(2^i)$

We will show that for ALL $i \geq 1$, $b(2^i) + m $ is Not multiple of $n.$

Let's check $b(2^i) + m $ 

= $b(2^i) +  n(X) - a(2^i)$ = $2^i(b-a) + n(X)$

$2^i(b-a) + n(X)$ is Not divisible by n. Because $2^i(b-a)$ is Not divisible by n due to the Theorem 1 (NOTE that $1 \leq b-a \leq n-1$ and $i \geq 1$,  ) 

 

So, this proves that If you take any Two binary strings $u,v$ whose decimal value is between 1 and n-1 and $decimal(u) \neq decimal(v)$ then for ALL strings $w \neq \epsilon$ if  $uw \in L$ then $vw \notin L.$

This shows that every number from 0 to $n-1$ is mutually distinguishable. 

 

---

Useful relevant links :

https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n/22282792

https://www.sciencedirect.com/science/article/pii/S0022000004000200/pdf?md5=d6888310e29849b6406cee916342ef9a&pid=1-s2.0-S0022000004000200-main.pdf

 

https://cs.stackexchange.com/questions/85850/minimum-number-of-states-in-dfa-accepting-binary-number-with-decimal-equivalent

Let the i/p alphabet = {0,1} for the following questions :

$\color{red}{Q) \mathbf{About\; String \;Lengths : }}$

$\color{green}{i) \text{ Length of the strings exactly = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Length of the strings atmost = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{iii) \text{ Length of the strings atleast = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{iv) \text{ Length of the strings divisible by n  :  }}\color{blue}{\text{  n}}$

$\color{green}{v) \text{ Length of the strings atleast = m & atmost = n  :  }}\color{blue}{\text{  n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

 

$\color{red}{Q) \mathbf{About\; Prefix\; Lengths : }}$

$\color{green}{i) \text{ Length of the prefix  = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Length of the prefix  = m & total length of the string exactly = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the prefix  = m & total length of the string atmost = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the prefix  = m & total length of the string atleast = n :  }}\color{blue}{\text{  max(m,n)+2}}$

$\color{green}{v) \text{ Length of the prefix  = m & total length of the string divisible by n :  }}\color{blue}{\text{ m+n+1}}$

 

$\color{red}{Q) \mathbf{About\; Suffix\; Lengths : }}$

$\color{green}{i) \text{ Length of the suffix  = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{ii) \text{ Length of the suffix  = m & total length of the string exactly = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the suffix  = m & total length of the string atmost = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the suffix  = m & total length of the string atleast = n :  }}\color{blue}{\text{  max(m,n)+1}}$

$\color{green}{v) \text{ Length of the suffix  = m & total length of the string divisible by n :  }}\color{blue}{\text{ m+n}}$

 

$\color{red}{Q) \mathbf{About\; Substring\; Lengths : }}$

$\color{green}{i) \text{ Length of the substring  = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{ii) \text{ Length of the substring  = m & total length of the string exactly = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the substring  = m & total length of the string atmost = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the substring  = m & total length of the string atleast = n :  }}\color{blue}{\text{  (n-m+1)*(m+1)}}$

$\color{green}{v) \text{ Length of the substring  = m & total length of the string divisible by n :  }}\color{blue}{\text{ (n)*(m+1)}}$

 

$\color{red}{Q) \mathbf{About\; Fixed\; position : }}$

$\color{green}{i) \;\;n^{th}\text{ position from the left side of the string is fixed to ‘0’  : }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \;\;n^{th}\text{ position from the right side of the string is fixed to ‘0’  : }}\color{blue}{\text{ }2^{n}}$

 

$\color{red}{Q) \mathbf{About\; Number \;of\;occurances : }}$

$\color{green}{i) \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Number of ZERO’s in the strings atmost = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{iii) \text{ Number of ZERO’s in the strings atleast = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{iv) \text{ Number of ZERO’s in the strings divisible by n  :  }}\color{blue}{\text{  n}}$

 

let two positive integers m and n, neither m divides n nor n divides m:

$\color{green}{v) \text{ Number of ZERO’s in the strings divisible by n and m  :  }}\color{blue}{\text{ LCM(n,m) }}$

$\color{green}{vi) \text{ Number of ZERO’s in the strings divisible by n or m  :  }}\color{blue}{\text{ LCM(n,m) }}$

$\color{green}{vii) \text{ Number of ZERO’s in the strings divisible by n but not by m  :  }}\color{blue}{\text{ LCM(n,m) }}$

 

let two positive integers m and n, either m divides n or n divides m:

$\color{green}{viii) \text{ Number of ZERO’s in the strings divisible by n and m  :  }}\color{blue}{\text{ MAX(n,m) }}$

$\color{green}{ix) \text{ Number of ZERO’s in the strings divisible by n or m  :  }}\color{blue}{\text{ MIN(n,m) }}$

$\color{green}{v) \text{ Number of ZERO’s in the strings divisible by n but not by m  :  }}\color{blue}{\text{ MAX(n,m) }}$

 

$\color{red}{Q) \mathbf{About\; independent Data items : }}$

While multiplying, you should take care of productive states.

$\color{green}{i) \text{ no.of ZERO’s are exactly ‘n’ and no.of ONE’s exactly ‘m’  : }}$

$\;\;\;\color{blue}{ \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}} = \color{magenta}{\text{  (n+1)+(1 DS)}}$

$\;\;\;\color{blue}{ \text{ Number of ONE’s the strings exactly = m  :  }}\color{blue}{\text{  m+2}} = \color{magenta}{\text{  (m+1)+(1 DS)}}$

$\color{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$

 

$\color{green}{ii) \text{ no.of ZERO’s are exactly ‘n’ and no.of ONE’s atleast ‘m’  : }}$

$\;\;\;\color{blue}{ \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}} = \color{magenta}{\text{  (n+1)+(1 DS)}}$

$\;\;\;\color{blue}{ \text{ Number of ONE’s the strings exactly = m  :  }}\color{blue}{\text{  m+2}} = \color{magenta}{\text{  (m+1)}}$

$\color{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$

 

Supported Documents : https://drive.google.com/open?id=1haPRlS78p7RA7ugMhaK9Li6370ZjaEcx

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$

We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the final state for divisibility by $3$. If we add a '0' transition from this state to another state and make it FINAL, we get divisibility by $6$ as a '0' at end ensure number is divisible by $2$ and also retains the property that the number is divisible by $3$ which makes it divisible by $6.$ Add one more state like this and we get numbers divisible by $3\times 2\times 2 = 12.$ Thus we need $5$ states in the minimal DFA for divisibility by $12.$

---

The above construction works because in the DFA for divisibility by $3$, there will be no outgoing edge on $0$ to the final state from any other state. This is because no number not divisible by $3,$ when multiplied by $2$ will become divisible by $3$ (holds for any odd number). But there will be self edge on the final state for '0' - when we add the new state for divisibility by $6,$ we remove this edge and make it go to the new FINAL state. 

---

The above construction works in general too. To check if a binary number is divisible by $n$

1. If $n$ is a power of $2$ we need $\log_2 n+1$ states in the minimal DFA 
2. If $n = 2^k \times m,$ where $m$ is odd, then we need $k + m$ states in the minimal DFA

PS: To be proved: To check a binary number for divisibility by any odd number $k$ requires $k$ states in the minimal DFA.

---

To find the minimal number of states in the DFA accepting binary strings divisible by $m$ and $n:$

Here, we have to check divisibility by $m$ and divisibility by $n$. So, we can take this as divisibility by $\text{LCM}(m,n).$

---

To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$

These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear. 

Part 2 is added now...

Decidability Slides Updated

Day	Date	Contents	Slides	Assignments
1	Sep 27	Regular Language- alphabets, language(set of strings), language class or language family All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable recursive set of languages outside recursively enumerable languages  Finite Automata- Deterministic Automata and Non Deterministic Automata- mathematical representation Number of DFA's possible with two states over {0,1} What do you know about Regular language? 1.) Finite automata acceptance 2.) Deterministic finite automata acceptance 3.) Has an equivalent regular expression Operators in regular expression, Deterministic and Non Deterministic languages are not same in CFL Pumping Lemma- used to check if a language is not regular Regular set --> Pumping lemma Definition with examples Methods to check if a language is regular: (i) Pumping lemma- one way (ii) Regular expression/ Finite automata/ Regular grammar- two way (iii) Myhill- Nerode theorem- equivalence relation for this theorem, distinguishing string Difference between context-sensitive and recursive language- space complexity is linear in LBA, find an example for language accepted by TM but not LBA
2	Sep 28	Product automata If L is regular: Is L empty? Is L equal to sigma*? Is reverse of L regular? Is first half(L) regular? More examples to check whether grammar is regular or not. Regular Grammar: G=(V, T, P, S) Left linear grammar- only one non-terminal on left of each production Right linear grammar- only one non-terminal on right of each production All linear grammars are not regular, but all regular languages are either left linear or right linear. Context Free Grammar- Pushdown Automata = NFA + Stack L={a^n c b^n | n >= 0} not regular Push all a's into stack, if c is reached do not do anything on stack, now for each b pop an a from stack. If stack is empty finally then string is accepted if the input is over. PDA- mathematical representation, accepts all regular languages Acceptance by final state and acceptance by empty stack- both are eqivalent in case of PDA In Deterministic PDA acceptance by empty stack is a subset of acceptance by final state.
3	Sep 29	Half(L) is regular - how to construct DFA for Half(L) Squareroot(L) is regular Square(L) is not regular
4	Sep 30-Oct 2	Solve GO pdf questions on regular language,regular expressions and context free languages
5	Oct 3	Pushdown Automata Given a PDA which accepts by empty stack, how to convert it to PDA accepts by final state. {aab,aa,a} - Can you make PDA that accept by empty stack? NFA = DFA < DPDA < PDA PDA by empty stack = PDA by final state DPDA by empty stack < DPDA by final state {a,aa,aab}- If strings are prefixes then it cannot be accepted by DPDA by empty stack. Which is more powerful? DFA or DPDA by empty stack These two are not comparable. There are some languages by DPDA empty stack which cannot be accepted by DFA and vice-versa. Language of [DPDA by empty stack] = LR(0) Assignment: Take an input executable and an input 'w' for that and outputs "yes" when the executable finish running.
6	Oct 4	Assignment explanation: FSM, PDA - no chance for infinite loop How to check PDA is going to infinite loop? - we can detect it from PDA configuration Turing Machine Extra power for TM (i) can modify tape (ii) can move left TM can go to infinite loop. Case 1: It always outputs [correct answer]  Decidable , Language is Recursive All problems solved by FSM Case 2: It always outputs "Yes" for "Yes" case Semi-decidable, Language is Recursively Enumerable Halting problem Case 3: It cannot output "Yes" for all "yes" cases Not even semi-decidable, Language is not Recursively Enumerable Complement of Halting problem. Given a TM and a word whether that TM does not stop running? Outputs no for all "no" cases but for all "yes" cases we cannot print "yes". Both case 1 and case 2 are Undecidable Case 4 does not exist ie, it always outputs "no" for all "no" cases(included in case 3) Halting problem is both semi-decidable and undecidable. Complement of Halting problem is not even semi-decidable and it is undecidable. LBA - Linear Bounded Automata The tape space is limited, it is bounded by some multiple of input string. Eg: divisible by 10(it can be any multiple of 10) What about acceptance of empty string in LBA? Empty string is added as special case.(no linear bound for empty string) Not even Recursively Enumerable is largest set of languages. Given a two DFA M , N ,Is L(M)=L(N)? Is L(M) subset L(N)? L(M) ∩ L(N)' = Φ then L(N) AND L(N) ∩ L(N)' = Φ then L(M) = L(N) Given two DPDA's can we say if they are accepting the same language or not?- Decidable(recent study) Checking if CFL is empty?- Decidable
7	Oct 5	Closure properties of language families- Union, intersection, compliment, reverse for Regular, DCFL, CFL, CSL, Recursive, Recursively Enumerable Counter examples for proving not closed L1 and L2 are two DCFL's. Is L1 ∩ L2 a DCFL? - Undecidable(no algorithm to detect this) If L2 is regular then it is decidable(always an Yes) Trivial property - either the property satisfied by all elements of set or none of the elements satisfy that property Non-trivial property - some elements satisfy and some elements do not satisfy Non- monotonic property- (i)"some property holding element must be a proper subset of "some" property violating element (ii) non-trivial Examples of trivial, non-trivial and non-monotonic properties on recursively enumerable set RICE'S THEOREM: 1) Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable 2) Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable Examples of Rice's theorem Dovetailing method- example: Whether a language L accepted by TM, M has atleast 5 strings?- semi-decidable Check if a language L is infinite?- not a non-monotonic property- can be proved by reduction from a 'not even semi-decidable' language. If PDA is accepting strings of lenth n and 2n, using PL it can be proved that PDA is infinite- where n is pumping lemma constant
8	Oct 6	More examples on Rice's theorem Reducing a problem to Halting problem or non-halting problem Some trivial and non trivial properties of Turing machine description and proof for decidability(cannot use Rice's theorem- it is about TM and not about language accepted by TM) If TM is restricted form writing on tape, what language can it accept?- Regular language Read-Only tape- set of regular languages- Can it accept anymore language- No, there is no extra power on moving left Multi-R/W Tape- No extra power(adds to time complexity) Non- determinism- No extra power How to detect infinite loop in a program? - search for keywords or by checking repeated memory sequence - TM can output "No" for some cases but not for all inputs. TM movement in one direction only- finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.

 

 

PLEASE CHECK MY UNDERSTANDING:-

1. Halting Problem:-
a) A turing machine halts after running for exactly k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

b) A turing machine halts after running for atmost k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

c) A turing machine halts after running for atleast k steps on any input
This is SEMI-DECIDABLE, as we can construct a Turing Machine for this problem and it can loop forever.

2. State Entry Problem:-
a) A turing machine visits a particular state "q" exactly k times on any input
We can simulate this problem using Bi-tape or Bi-Track Turing Machine. 1 tape/track can be used to simulate the given turing machine specification and the next track/tape can be used as a counter. We increment the counter whenever we come across that state. But there is chance for looping as that particular state can be visited after very large number of steps. So, this is SEMI-DECIDABLE.

b) A turing machine visits a particular state "q" atmost k times on any input
SEMI-DECIDABLE(Same as above)

c) A turing machine visits a particular state "q" atleast k times on any input
SEMI-DECIDABLE(Same as above)

d) A turing machine visits a particular state "q" after exactly k steps on any input
Number of Steps are finite. So, DECIDABLE.

e) A turing machine visits a particular state "q" after atmost k steps on any inpur
Again, Number of Steps are finite. So, DECIDABLE.

f) A turing machine visits a particular state "q" after atleast k steps on any input
It may visit "q" after a very large number of steps. So, looping possible. Though we can construct a Turing Machine for this. Hence, SEMI-DECIDABLE.

g) A turing machine visits exactly n states on any input
There can be many redundant states and the turing machine might visit only some states for a particular input. For all inputs, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

h) A turing machine visits atmost n states on any input
SEMI-DECIDABLE(Same as Above).

i) A turing machine visits atleast n states on any input
SEMI-DECIDABLE(Same as Above).

3. Acceptance Problem:-
a) A turing machine accepts strings of length exactly "n" 
Basically, Halting Problem reduces to this. Hence, SEMI-DECIDABLE.

b) A turing machine accepts strings of length atmost "n" 
SEMI-DECIDABLE(Same as Above).

c) A turing machine accepts strings of length atleast "n" 
SEMI-DECIDABLE(Same as Above).

4. PROBLEM RELATED TO CONTROL OF TURING MACHINE:-
a) The control of a turing machine moves right exactly n times on any input
If it was 1 time, we can easily decide. Also if it was for 1 particular string, we can decide. But for all strings in the Language, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

b) The control of a turing machine moves right atmost n times on any input
SEMI-DECIDABLE(same as above).

c) The control of a turing machine moves right atleast n times on any input
SEMI-DECIDABLE(same as above).

5. PROBLEM RELATED TO REPLACEMENT OF CHARACTER IN TURING MACHINE:-
a) A turing machine replaces the characters on the tape exactly n times on any input 
If it was for 1 particular string, we can decide. But for all strings in the Language, it is kinda difficult to decide as we might have to run the turing machine for all possible inputs from the Alphabet set. Though we can simulate the problem statement using a Bi-tape or Bi-Track Turing Machine where the 2nd tape/track acts as the counter. Hence, SEMI-DECIDABLE.

b) A turing machine replaces the characters on the tape atleast n times on any input
SEMI-DECIDABLE(same as above).

c) A turing machine replaces the characters on the tape atmost n times on any input
SEMI-DECIDABLE(same as above).

Nice papers with examples:

http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-reductions-rice.pdf

http://people.cs.aau.dk/~srba/courses/CC-08/rice-uk.pdf

Important Ones

https://gateoverflow.in/questions/theory-of-computation?sort=featured

More Questions

http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/assign6/pb9.html

Problem Set 1

Problem Set 2