- Give an example of a Finite State Automata $M$ such that $L(M)$ is all palindromic strings of length $6$.
Solution attempt: I was thinking we could simply define a FSA where all strings of length $6$ end up in a unique halting state, and then for each of the $8$ palindromic strings we just define the corresponding halting state to be an accepting state. I can't find a problem with this but I just have a feeling there is one because it's such an easy and inelligant solution.
- Suppose $M$ is a FSA and $L(M)$ is infinite. Show that the number of strings in $L(M)$ of length $n$ or less grows linearly with $n$.
Solution attempt: the maximal number of strings of length $n$ is $2^n$, so the maximal number of strings of length at most $n$ would be the sum of the first $n$ powers of $2$ which is $2^{n+1}-1$. But this does not grow linearly with $n$ so I'm not sure where to go from here.
- Prove there is no FSA $M$ such that $L(M)$ consists of all twice-repeated strings.
Solution attempt: I'm afraid I have no idea how to approach this.
Thanks in advance for any help.
For (1) you're right, assuming that your alphabet is finite. A finite language is always regular, so in particular a language where the length of a word is bounded will always be regular. You can reduce the size of your automaton a bit by combining all of the states that can't possibly lead to acceptance (which will happen once you read a 4th, 5th or 6th symbol that doesn't match the 3rd, 2nd or 1st) into a common discard state
For (2) you're right too -- what you're being asked to prove is not true, so you cannot get through with a proof. (An easy counterexample is that the language $\{\mathtt 0,\mathtt 1\}^*$ is generated by a finite automaton, but it has $2^n$ elements of length $n$, which is supralinear.
For (3): Perhaps you have learned the Myhill-Nerode theorem, which resolves this easily. Alternatively, the pumping lemma for regular languages can do it too, but is generally more cumbersome to work with in my opinion.