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.

  • 1
    $\begingroup$ Sounds like to pumping lemma for regular langugages.... $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – goblin Oct 16 '13 at 22:39
  • $\begingroup$ 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. $\endgroup$ – user27546 Oct 16 '13 at 22:43
  • $\begingroup$ You're welcome! $\endgroup$ – goblin Oct 16 '13 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.