First-order Logic and the Star-Free Languages

[DRAFT]

FO sentences as grammars

Recall the following FO sentence from the introduction:

\[\varphi=(\forall x)[a(x)\rightarrow\neg(\exists y)[b(y)\land x<y]]\]

...and the set of strings \(L\) over \(\Sigma=\{a,b,c\}\) such that no \(a\) ever precedes a \(b\), anywhere in the string:

\[ L = \{accca,cccc,bcccb,bbccca,...\}.\]

Take a moment to convince yourself that \(L\) is exactly the set of strings that satisfies \(\varphi\). To do this, show yourself that (the models of) a few strings in \(L\) satisfy \(\varphi\), and also that (the models of) a few strings in \(\overline{L}\) do not satisfy \(\varphi\).

Let's look at some more.

• Write an FO sentence that describes the set of strings that do not end in a \(b\).
• Write an FO sentence that describes the set of strings in which \(a\) cannot be followed by another \(a\), unless a \(b\) intervenes. That is, \(caccccac\) is not in the language but \(caccbccca\) is (think the obligatory contour principle-type constraint with blocking).
• What about an FO sentence that describes \((ab)^n\)? Hint: we can define a successor relation \(\triangleleft\) from \(<\) using the following equation \[x\triangleleft y:= x<y\land\neg(\exists z)[x<z\land z<y]\]
• What about an FO sentence that describes \(a^nb^n\)?