2021-09-03 exam, 2nd exercise

2021-09-03 exam, 2nd exercise

by TOMMASO GOMIERO -
Number of replies: 3

Good evening

Doing this exercise, I found two regular expressions for L1 and L2 (so they are regular languages).

Looking at L3 , using pumping lemma on the string abnabna ∈ L3, i concluded that the language is not regular. But looking at the language's structure, it also seems to me that the third one is the intersection of the first two languages, which are regular, so it should also be regular. What am I doing wrong? Is L3 actually the intersection of the first two languages? 

Thanks for the attention

In reply to TOMMASO GOMIERO

Re: 2021-09-03 exam, 2nd exercise

by NORDIN MOHAMED MOHAMED SHAFIQ ELBASTWISI -
Hi Tommaso! I believe \( L_1 \) is nonregular, that's why the intersection closure still works. I wonder what RE you got for it.
In reply to NORDIN MOHAMED MOHAMED SHAFIQ ELBASTWISI

Re: 2021-09-03 exam, 2nd exercise

by TOMMASO GOMIERO -
Hi! I noticed that L1 is the set of languages that have odd length (at least 3) and equal first and last symbols, the characters in the middle of the string are not really important, since there is no restriction on u and v other than their length. So, the RegEx i found is: 

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
 
 
In reply to TOMMASO GOMIERO

Re: 2021-09-03 exam, 2nd exercise

by DAVIDE PINZAN -
As you might have guessed the last language is not the intersection. The first language, as you said, is "all odd strings of length greater than or equal to 3 that end and begin with the same symbol". The second language is "all strings in which a certain symbol appears at the beginning, at the end and at least once anywhere between the two". So for the intersection you need to combine those two propositions with a logical AND and the resulting language would be something like "all odd strings of length >=3 that end and begin with the same symbol and have that same symbol somewhere else inside the string". The tricky part is that symbol Y represents different things in each of the languages. L3 puts an additional constraint saying that the character at the beginning and at the end of the string needs to be exactly at the center too, which is not required by the actual intersection.