# Translating English into First Order Logic

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.

• Sounds like to pumping lemma for regular langugages.... – DanielY Oct 16 '13 at 8:11

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))$

To start off this is suppose to be a comment in response to user18921, however I cannot find add comment under his post. I'm not sure if the OP still needs this question answered or not. I'm wondering how would you (user18921) translate it into logic? I can't seem to come up with the translated form. I tried to answer this question before, but I keep forgetting which set would belong to what and where the existential quantifiers and universal quantifiers would go.

• Done. Yeah the translated form is sprawling and enormous, I had to break it up into three lines using asterisks, so I'm not surprised mistakes kept creeping in. I really think that first translating into "logical English" is key. – goblin Oct 16 '13 at 22:39
• Wow. I'm amazed you actually managed to get something that even looks reasonable. I am starting to see how you got to that answer. Thanks for taking the time to respond. – user27546 Oct 16 '13 at 22:43
• You're welcome! – goblin Oct 16 '13 at 22:45