# Is language bin(n)bin(2^(k+1) n + 1)^R context-free

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.

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