0
$\begingroup$

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm having trouble with the proof. Our symbols are {a, b}.

I allowed L = $\{(ab)^{*{\frac{n}{2} - 1}} aa (ab)^{*{\frac{n}{2} - 1}}\}$. I know the format of the language is wonky, and will be talking to my professor about it tomorrow. For the proof, I allowed $\frac{n}{2} - 1$ to be the combination of symbols before and after the two elements. So, using the Pumping Lemma's condition that |uv|≤ n, I allowed $u = \frac{n}{2} -1$ and $v = n^2$ (for aa); this is obviously greater than n, but I'm having trouble understanding how to choose $u$ and $v$. Is my assignment for these parameters correct?

$\endgroup$
5
  • $\begingroup$ I tried to guess what you intend. I may have guessed wrong. But the pumping lemma is not stated everywhere with the same notations, for the string chosen, for its length, for the pumping length, for the substrings the string is divided into ... It is better to define that clearly when asking a question. And you might have avoided mixing string and integers. If u and v are strings, u cannot be equal to n/2-1. My answer is intended to be incomplete, but conyains hints. Howver, if it is unclear, ask for what you do not understand. $\endgroup$
    – babou
    Mar 7, 2014 at 8:09
  • $\begingroup$ You should edit your question. First you should add the tag homework. Then you should make corrections regarding your attempted use of the pumping lemma, and avoid making strings equal to integers. $\endgroup$
    – babou
    Mar 7, 2014 at 10:24
  • $\begingroup$ Definitely don't use the homework tag.. $\endgroup$
    – Raphael
    Mar 7, 2014 at 13:20
  • $\begingroup$ cc @Raphael - Sorry about the "homework" tag suggestion. It is used on some other SE sites, and I got confused. But the question should definitely be edited to show understanding of the pumping lemma, which is a necessary step before doing anything else. You may use information and explanations from the reference question for that purpose. $\endgroup$
    – babou
    Mar 7, 2014 at 13:45
  • $\begingroup$ You should define your language as $L = \{(a b)^n a a (a b)^n \colon n \ge 1\}$ (if I understand right). That is easier to work with. $\endgroup$
    – vonbrand
    Mar 7, 2014 at 15:42

1 Answer 1

0
$\begingroup$

$u$ and $v$ are supposed to be strings such that $uv$ is a prefix of a string in the language longer than $p$ symbols, $p$ being the pumping length. Furthermore, you do not get to choose them. All you know is that their total length does not exceed $p$ and they are prefix of a word $x$ in the regular language, of length $n$.

You do not get to choose them because they are existentially quantified in the statement of the pumping lemma ... you could choose them if they were universally quantified. If you do not understand this last remark, just ignore it.

What you can choose is the value of $n$ and the string $x=uvw$ of size $n$ that will be used for pumping. You choose $n$ in relation to the pumping length $p$ which depends only on the regular language.

I would suggest to choose $n$ quite big, so that you make sure $uv$ is in the first half of the string $x$, since $| uv| ≤ p$.

I would also choose my string $x$ with an appropriate pattern of a and b ... and then check what happens when I pump. It may seem odd, but you have to get even with that problem.

$\endgroup$
5
  • $\begingroup$ Your answer does not offer anything beyond the answers to the reference question; yet, the OP has a quite specific question. $\endgroup$
    – Raphael
    Mar 7, 2014 at 7:14
  • $\begingroup$ @Raphael I do not understand your comment. He is saying he does not know how to choose $u$ and $v$, and I replied that they are not his to choose, nor are they integers. He has to choose the string he works on, and if greater than the pumping length, the lemma ensures the existence of strings $u, v, W$ such that ... I give him size hint, suggest choosing the a/b pattern adequately, and a bit more. Some of what he does make no sense to me. What specific question did I miss? I tried not to give the whole answer, so that he can learn, or ask more questions. $\endgroup$
    – babou
    Mar 7, 2014 at 8:04
  • $\begingroup$ I was referring to this question. You seem to give general explanation similar to the one there so, arguably, your answer is effectively a vote to close as duplicate. $\endgroup$
    – Raphael
    Mar 7, 2014 at 9:30
  • $\begingroup$ @Raphael Not quite a duplicate. We do get many pumping problems, and it is true that often the OP has trouble understanding the lemma itself. But then the problems differ in the way they are to be handled. Tried to explain reading the lemma, but also to give several hints regarding the specific solution. One hint is a bit hidden in my last sentence. If you close that, we might as well close nearly all homework questions. I would leave them open for whoever wants to spend some time teaching, unless it is exactly the same problem as a previous question. That is what the homework tag is for $\endgroup$
    – babou
    Mar 7, 2014 at 10:22
  • $\begingroup$ We don't use the homework tag. As for the rest, I did not read your answer closely but from skimming I did not see the specifics you address. My point was not to close the question, by the way, but that your answer was not appropriate (which may not be the case). $\endgroup$
    – Raphael
    Mar 7, 2014 at 13:21

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