$(aba)^{*}$ is first-order definable?

Question

I had been asked to show that $(aba)^{∗}$ is FO-definable over the signature $\{Q_a, Q_b, <, S\}$.
But I read that "A language is first-order expressible iff it is star-free."

But clearly the language I have been asked about contains "*" (star). What am I missing? Which FO-formula $\phi$ captures the language such that the set of words satisfying the formula give me the language $(aba)^{∗}$?

Can a formula like this be given as a valid formula for the collection of words?

$(Q_a(0) \land Q_a(2) \land Q_a(3) \land Q_a(5) \land ... \land Q_a(n-1)) \land (Q_b(1) \land Q_b(4) \land Q_b(7) \land Q_b(10) \land ... \land Q_b(n-2)) \land (n = |S|)$

Answer 1

Remember that a language is $*$-free if it has some definition not using Kleene's $*$. So just because one definition uses the $*$, doesn't mean the language isn't $*$-free.

It might help to start with an easier example: the language $(ab)^*$. This is first-order definable: we can write a sentence which says:

• The first element is $a$,

• The last element is $b$,

• Every $a$ is followed by a $b$, and

• Every $b$ is preceded by an $a$.

And we can come up with a $*$-free description of $(ab)^*$ (exercise).

Now, do you see a similar way to get a first-order definition of your language?