pumping lemma

pumping lemma

by MAULIK RUPESHBHAI SOMPURA -
Number of replies: 9

I am struggling with the pumping lemma exercise and couldn't find a solution online. I’ve attached a photo of my attempt, where I’ve tried to identify the language and wrote my reasoning just to identify the language.

Could you kindly confirm if my approach is correct? Also, in the question, do X, Y, and Z act as separators in the string?

I assumed they do but am unsure.

Thank you for your guidance.


In reply to MAULIK RUPESHBHAI SOMPURA

Re: pumping lemma

by Giorgio Satta -

Before I make my comments, is there any student who can anyone answer to this message?

X, Y, Z are not special symbols, they are variables that stand for any symbol from Sigma.

One comment: in the solution of language L1, if L1 is not a regular language, then the student is expected to apply the pumping lemma using mathematical notation, as we have always done in class and in the exercise collection. Informal explanation like 'FSA cannot count' is a good intuition but will not be accepted as a mathematical argument at the final exam.

In reply to Giorgio Satta

Re: pumping lemma

by FARZAD SHAMI -
I hope these answers are correct.

L1 = Since |u| = |v|, For uYv, the strings with at least one occurrence of the (a, b, c) for the base case and 3, 5, ... for the others
so we can write it as
a(a+b+c)[(a+b+c)(a+b+c)]*a + b(a+b+c)[(a+b+c)(a+b+c)]*b + c(a+b+c)[(a+b+c)(a+b+c)]*c

For L2, we can write
a(a+b+c)*a(a+b+c)*a + b(a+b+c)*b(a+b+c)*b + c(a+b+c)*c(a+b+c)*c

The L3 is the intersection of two REG languages, and since the REG class is closed under intersection, the L3 is REG, too.
In reply to MAULIK RUPESHBHAI SOMPURA

Re: pumping lemma

by Shabnam Zareshahraki -
Hello!
This is my solution to this question. I would also appreciate it if you could comment on mine.
In reply to Shabnam Zareshahraki

Re: pumping lemma

by UMBERTO BIANCHIN -
I think L1 belongs to REG. You can think about it as the language composed by strings that start and end with the same symbol, and between those symbols you must have a "substring" of odd length (so you can divide it in two equal length parts with one symbol between them). You can prove this with a NFA or with a reg. expression. For the reg. expression you have something like that: define R = a+b+c
aRa + aRRR(RR)*a + bRb + bRRR(RR)*b + cRc + cRRR(RR)*c
L3 is not in REG and you have to apply the pumping lemma, but I think you have to consider two cases (say you take string w = a b^n a b^n a):
the first in which y contains the first symbol of the string, and the second in which y contains symbol only from the first block of b. Then both of them could be solved taking k = 0.
In reply to UMBERTO BIANCHIN

Re: pumping lemma

by MAULIK RUPESHBHAI SOMPURA -
I think for L1 your intuition about L1 as a language where strings start and end with the same symbol and have an odd-length substring in between (allowing division into two equal parts with a middle symbol) is valid but represents only a subset of L1. correct me if I am wrong here. The actual definition of L1 includes an additional constraint: the lengths of the substrings |u| and |v| must be equal. which means u and v can have any length (including even or zero), as long as they are equal in length. Finite automata and regular expressions cannot handle this kind of unbounded counting and comparison.

Why Odd-Length Substrings Work for a Special Case:
If you only focus on odd-length substrings between X and Z, your reasoning can hold:
An odd-length string can be split into two equal parts with one middle symbol (u and v).
This avoids the issue of explicit counting, because the middle symbol acts as a fixed separator.
As professor mentioned the X,Y,Z are not special symbols, it is a variables.

Your Intuition is not wrong—it simply describes a subset of L1 (strings with odd-length substrings between X and Z). The issue arises because L1 is more general, requiring arbitrary equality of |u| = |v| which makes it non-regular. I may be wrong somewhere I am open to any feedback.

Thank you.
In reply to MAULIK RUPESHBHAI SOMPURA

Re: pumping lemma

by FILIPPO MAZZAROTTO -
We can prove that u and v have the same length if and only if uXy is odd.

Bi induction on length of u.

Basis: |u| = 0. The overall string is just X, with length 1, so odd

Inductive step. Assume wa = u. By inductive hypothesis

|w| X |w|is odd. Then |wa|X|wa| = |w| X |w| +2. Odd number plus an even number is still odd, so the statement holds.

I'm typing on mobile sorry for bad formatting.

In reply to MAULIK RUPESHBHAI SOMPURA

Re: pumping lemma

by UMBERTO BIANCHIN -
I'll try to explain myself better. u and v must have equal length. If they are both empty, you have w = XYZ and the only constraint you have is that X = Z, and the regular expression I wrote before cover this case. If the length is >= 1, in any case you have that uYv is an odd length string. Let's say |u| = |v| = k. We have that |uYv| = k + 1 + k = 2k + 1, which will be an odd number for any k >= 1. So for L1 you only have to verify that the first and the last symbol are equal and that the uYv substring has odd length, no matter what are u, v and Y.
I hope I was clear enough, thanks.
In reply to UMBERTO BIANCHIN

Re: pumping lemma

by Shabnam Zareshahraki -
I see your point on L1 being REG, but I cannot come up with a regular expression for L3. Since you say L1 is REG and L2 is REG, doesn't it follow that their intersection L3 is also REG? I'm not sure what I'm missing here!

This is the regular expression representing L1 = a((a+b+c)(a+b+c))*(a+b+c)a + b((a+b+c)(a+b+c))*(a+b+c)b + c((a+b+c)(a+b+c))*(a+b+c)c, if I understand you correctly.
In reply to MAULIK RUPESHBHAI SOMPURA

Re: pumping lemma

by Giorgio Satta -

Thanx everyone for the interesting discussion on this exercise.

You can find a discussion of this problem in the second part of lecture #27, available on a video recording at this link. To access those video recordings, see the instructions 'Videorecordings of lectures from past years' posted in the Class forum.

This exercise was also discussed in class this academic year.