Translating English into First Order Logic

Question

Translate the following into a formula of first-order logic. "A language L that is regular will have the following property: there will be some number N (that depends on L) such that if s is a string in L (a string is a sequence of characters) whose length is at least N then s can be written as $xyz$ where y is not the empty string and $xy^i z$ is in the language L for every nonnegative integer i."

can anyone help me with this? This is what I came up with so far and it's definitely not right...

My Guess: Universe of Discourse: Language N(x)= x is some number depending on L I(x)= x is non negative integer S(x)= x is string in L

for existential quantifier ill use "bE" and for universal quantifier ill use "bA"

Guess starts here: bEx(N(x) ^ (S(x) > N(x)) --> bEx bEy bEz((S(x)=xyz)^y does not equal S element empty set)) ^ bAx(I(x)

This is probably completely wrong; I don't really get it. Thanks for any input/help.

Answer 1

Before putting everything into symbols, try to rewrite the sentence in a more logical way. For example:

For all $L$, if $L$ is a language and $L$ is regular, then there exist $N$ and $s$ such that if

1. $N \in \mathbb{N}$, and

2. $s \in L$, and

3. $\mathrm{length}(s) \geq N,$

then there exist $x$, $y$ and $z$ such that

1. $s=xyz$

2. $x,y$ and $z$ are strings

3. $y$ is not the empty string

4. for all $i,$ if $i \in \mathbb{Z}$ and $i \geq 0$, then $xy^iz \in L.$

By the way, a good universe of discourse would be the universe of sets.

---

Edit. Here's one possible symbolization. If it looks hideous (which it does), try drawing it as a tree diagram and it will be better (no parantheses!). By asterisk I mean: next line!

• $\forall L(\mathrm{language}(L) \wedge \mathrm{regular}(L) \rightarrow *)$
• $\exists N \exists s(\mathrm{natural}(N) \wedge s \in L \wedge \mathrm{length}(s) \geq N \rightarrow *)$
• $\exists x \exists y\exists z(xyz=s \wedge \mathrm{string}(x) \wedge \mathrm{string}(y) \wedge \mathrm{string}(z) \wedge y \neq \mathrm{TheEmptyString} \wedge \forall i(\mathrm{natural}(i) \rightarrow xy^iz \in L))$