שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

guest (guest) 27 Jun 2010 11:52

Question 8:
L = {xy^zyx^}
y^ = y reverse.
x^ = x reverse.
|x|, |y|, |z| > 0;

The answers says this language is regular. why is that?

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

Jonathancito 27 Jun 2010 12:24

I think, and correct me if I am wrong, that this language is basically the language of the following regular expression

$00(0 \cup 1)00 \cup 01(0 \cup 1)10 \cup 10(0 \cup 1)01 \cup 11(0 \cup 1)11$

Obv., any word in L is in the language of the regular expression by determining that |x|=|y|=1.
In the other direction, it seems that words that are not in the language of the regular expression cannot be partitioned in a way that satisfies the conditions of L.

Please check correctness.

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

guest (guest) 27 Jun 2010 14:03

I still don't understand.
This is a correct regular expression if you know that |x|=|y|=|z|=1, but no-one said so, why can you assume that?
Why can't I take the word w=0^p1^p0^p+11^p+1010^p+11^p+10^p1^p and use the pumping lemma?

Clearly I'm wrong, I just don't understand why.

Thank you for your answers.

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

Jonathancito 27 Jun 2010 18:32

It seems that the w you suggest is not in L since obv. the last and first character of any word in L need to be identical.
In the pumping lemma you must choose a w that is in L.

And notice that a word x is in L if it can be partitioned to $xy^Rzyx^R$ in any way.
I am suggesting that any word that follows the regular expression can be partitioned in the specific way that I suggested and that any word that doesn't follow the regular expression can not be partitioned in any way that follows the rules of the language.

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

guest (guest) 28 Jun 2010 08:08

אני מצטערת, אני עדיין לא מבינה.
הייתה לי טעות במילה שרשמתי מן הסתם הבלוקים האחרונים התבלבלו לי התכוונתי לרשום
w= 0^p1^p0^p+11^p+1011^p+10^p+11^p0^p

בכל אופן, אני לא מבינה למה אתה יכול להניח שהגדלים שלהם הינם 1? הרי יש מילים כדוגמת
00111011100
ששייכות לשפה ופה לדוגמא
|x|=2, |y|=3, |z| =1
זה עדיין עונה על הדרישות שהשפה הגדירה, וזה לא מיוצג באמצעות הביטוי הרגולרי שהצגת.
אי אפשר לכתוב ביטוי רגולרי לכל הגדלים האפשריים של x,y,z…

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

dfhh (guest) 28 Jun 2010 10:49

because xy^ and yx^ are reverse of each-other
then the xy^zyx^ that they all in size at leat 1, is like
XzX^ that X is in size at leat 2 and z could be anything.
since z could be anything, we can look only at X at size 2, and the test of the X we say is part of the z..
so, only word that are XzX^ |X|=2 |z|>0 are in the languege, and that is the

00Z00 or 11Z11 or 01Z10 or 10Z01 that jonathan wrote..

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

guest (guest) 28 Jun 2010 11:29

תודה רבה, נראה לי שהבנתי.

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

Jonathancito 28 Jun 2010 14:54

Another great reason for you guys to help each other, it seems to work!

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

Tammy Dagan (guest) 28 Jun 2010 22:09

רק עוד שאלה קטנה בנושא בנוגע לביטוי הרגולרי שהוצע עבור השפה-
מדוע
z
הוא בגודל 1?
אי אפשר להגיד שהשפה היא האיחוד הבא?
00(0U1)(0U1)*00 U 11(0U1)(0U1)*11 U 10(0U1)(0U1)*01 U 01(0U1)(0U1)*10 ?
כלומר, מחייבים את
z
להיות בגודל של לפחות אחד, ולאחר מכן יש שרשור בלתי מוגבל של אותיות…?

תודה רבה!

Re: שאלה 8 ממבחן מועד א' סמסטר א' 2008 דרשוביץ

Jonathancito 29 Jun 2010 04:20

Yes, that's what I am meant to write but didn't.
Maybe that's what got ddfh confused but luckily guest was here to help.