Proving a Language is not Regular using Myhill-Nerode Theorem

I have the language $ L$ $ =$ {$ a$ $ =$ $ b$ $ +$ $ c$ $ |$ $ a$ , $ b$ , $ c$ are binary integers, and $ a$ is the sum of $ b$ and $ c$ }, with alphabet $ \sum =\left\{0,\:1,\:+,\:=\right\}$ . I need to prove that this language is not regular using the Myhill-Nerode Theorem.

I am able to prove it using the pumping lemma by using $ a$ $ =$ $ 111$ $ =$ $ b$ $ +$ $ c$ $ =$ $ 100$ $ +$ $ 11$ . This string has a pumping length of 2. I divide the string into $ x$ $ =$ $ 1$ , $ y$ $ =$ $ 1$ and $ z$ $ =$ 1=100+11. So if I pump $ y$ with $ i$ $ =$ $ 2$ , I change $ y$ to $ 11$ . Therefore, the string after pumping is $ 1111=100+11$ , which is not true, leading to a contradiction that violates the pumping lemma.

But I am not sure how I would approach this using the Myhill-Nerode theorem. I know the idea is to find an infinite set in $ L$ that is pairwise distinguishable. But I am not sure which set I could choose. Could I use the same sets as the ones I used with the pumping lemma or would it have to be something different?

Thank you!

Proving a language is not regular using the Myhill-Nerode Theorem

I have to prove that the following languages are not regular using the Myhill-Nerode Theorem.

$ 1)$ $ \left\{0^n1^m0^n\left|m,\:n\:\ge 0\right|\right\}$

$ 2)$ $ \left\{w\left|w\:element\:of\:\left\{0,\:1\right\}^{star}\:is\:not\:a\:palindrome\right|\right\}$

For the first question, I did the following:

I considered the set $ \left\{0^n1^m\left|m,\:n\:\ge 0\right|\right\}$ . To prove that this set is pairwise distinguishable by the original language, I said that for all $ m$ and $ n$ , $ 0^n1^m$ is distinguishable from all previous $ 0^i1^m,\:0\:\le i\le n-1$ because there exists a $ z=0^n$ such that $ 0^n1^mz$ is an element of the original language but $ 0^i1^mz,\:0\le i\le n-1$ is not an element of the original language.

I first want to ask whether this was indeed the correct way to do the proof?

I am also quite confused for the second question as I can’t even seem to find a string that is part of the language but is a palindrome. All the strings other than the empty string in that language are not palindromes. So I am quite confused on how to approach the problem.

Any help would be highly appreciated!

Does the master theorem applies to this recurrence?

The recurrence:

$ T(n) = pT(n/q) + \log n$

for p < q and p >= 2.

So, I’ve figured out it would fall into case 1, since we have $ n^{log_{q}p} = n^r $ , for $ 0<r<1$ , which would mean that $ f(n) = \log n$ would be dominated by a polynomial factor, i.e $ \log n = O(n^{r-e})$ for $ 0 > e < r$ . But according to my professor, this is wrong, and, even though it’s dominated, it isn’t by a polynomial factor. So, who’s right after all?

Impossible recurrence relation help with masters theorem, plus evaluation of complexity

I had an exercise to solve a recurrence relation in my exam, I think it was a tricky question but I am not 100% sure.

The recurrence was $ T(n) = 2*T(n) + \sqrt{n} +42 $ , it was specifically asked to be solved using the master theorem, and I wrote it cannot be solved using master theorem because it requires for b>1. Do you think is correct?

After that I had a small piece of code to evaluate, after a look at it I decided it was $ O(n^3) $

    for i in range(1,n):       j = i+1       while(j/n<=n):         k=1         while(k<=n):             constantFunction(4) # a function that executes in constant time             k=k+3         j=j+1 

In my opinion the function going from 1 to n, makes the while(j/n<=n) always be <=n as $ n-> infinity $ , which makes the other while inside execute until k<=n, k will grow fast and soon that while loop makes me wonder, will it stop ? I mean let’s assume n goes to infinity, then k will grow, but not as much as n, so it’ll be $ O(n^3)$ . Am I right?

Thank you

Recurrence relation (not solvable by the master theorem)

Consider the following recursion: $ \begin{cases} T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} &n > 1 \ O(1) &n = 1 \end{cases}$ .

The master theorem doesn’t work, as the exponent of $ \log n$ is negative. So I tried unfolding the relation and finally got the equation: $ T(n) = n[1 + \frac{1}{\log(\frac{n}{2})} + \frac{1}{\log(\frac{n}{4})} + … + \frac{1}{\log(2)}]$ .

I do not know how to simplify (inequalities to use???) from here. A trivial method would be to assume that all reciprocal of the log terms are $ < \frac{1}{\log(2)}$ , and since there are $ \log n$ terms, the summation of all the reciprocal-log terms is $ < \frac{\log n }{\log(2)} = \log_2 n$ , which gives $ T(n) = O(n \log n)$ . However this is a very poor approximation, as by the master theorem we can check that the time complexity for the recursive relation $ T(n) = 2T(\frac{n}{2}) + n$ is $ O(n \log n)$ . Can someone find a tighter correct upper bound?

What Makes A TM undecidable (using Recursion Theorem)

PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B.

B =“On input w:

  1. Obtain, via the recursion theorem, own description ⟨B⟩.
  2. Run H on input ⟨B, w⟩.
  3. Do the opposite of what H says. That is, accept if H rejects and reject if H accepts.”

I can not understand point 3 I want to know its logic

Does this have same logic as the halting problem where if we get a yes it loops forever so it does not halt and if it does not halt we get a no then it halts?