I'm at the beginning of Theoretical Informatics and I was given some tasks one of which is following...
Be $k\in \mathbb{N}$, show that following language $L$ with the alphabet $\Sigma = \{0,1\}$ is regular.
$L= \{w\mid w$ is $2k$ Symbols long and a Palindrome$\}$
In books and on the Internet the consensus is gernerally that Palindromes are not regular (reason is that Finite Machines can't remember much information) but here I am asked to prove it, therefore it should be true.
Why is that ? In my mind I found it impossible to construct a (Non-deterministic) Finite Machine with that properties.
Can someone give me a hint why this is true ?
This doesn't contradict the fact that the set of all palindromes is not a regular language, as you are given a fixed length for the palindrome. For each $k$, the corresponding language $L$ is finite and hence regular. If we write $L_k$ rather than $L$ to make the dependency on $k$ explicit, the union $\bigcup_k L_k$ is not a regular language, but each $L_k$ is.