I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\text{bin}(n)$ is the representation of $n$ in base 2. I need to determine if this language is regular, context-free or not and prove. I thought I could use the complement of $L_1$, but I can't get any intuition in this approach.

  • $\begingroup$ What is $n$? Any natural number? $\endgroup$
    – John L.
    Jun 7 '20 at 6:02
  • $\begingroup$ @JohnL. yes, n is in natural numbers $\endgroup$ Jun 7 '20 at 9:43
  • $\begingroup$ Isn't bin(2^k n) = bin(n) 0^k ? $\endgroup$ Jun 7 '20 at 10:30
  • $\begingroup$ @HendrikJan so it's just adding another 0? $\endgroup$ Jun 7 '20 at 10:33
  • $\begingroup$ @bluerabbit Not just one, but k+1 zeroes, it seems. also don't forget its actually bin(2^{k+1} n + 1). $\endgroup$ Jun 7 '20 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.