Automata Theory: Prob # 66 from practice booklet

[brianhead]

Originally Posted by R0jkumar

From the very definition of L1, a string x is in L1 if and only if there is a substring of x that is in L. Your language a^nb^n certainly has a substring that belongs to L and hence a^nb^n is a subset of L1 but not the entire set. In other words by using L1 = a^nb^n you are showing that if x belongs to L1, then x contains a substring that belongs to L but you have to show the converse as well. That is you have to show that given a string x belonging to L, if you add any string at the beginning and at the end , you should be able to get a string in L1.But thats wont be true in the case of L1=a^nb^n since if i take any string of a's and b's and add any string at the beginning and the end, i am not necessarily going to get a string of a's followed by b's such that the number of a's and b's are equal. Hope that helps.

I get it.
thank you very much, R0jkumar

[taro_curly]

I solved #66 in a not entirely rigorous way.

We are given that L1 contains L as a substring. Since we know L is regular, by Pumping Lemma, we can split L into xy^nz where we can n can be any integer and xy^nz will still be regular.

Since every string in L1 contains L as a substring, we can have a situation like this:

(w1)L(w2) where w1 and w2 are strings.

Even here, we can write L1 = (w1)xy^nz(w2) and pump n.

Therefore, if L is regular, then by Pumping Lemma, L1 is regular.

therefore, I) is true

Using similar logic, we can show II) is true

If we look at the options, if I and II are both true, the answer can only be E) I, II, III are true.

Thus, we would not need to evaluate III. Incidentally, I do not know how to prove or disprove that statement.

Can anyone help?

[gttts23]

Originally Posted by taro_curly

I solved #66 in a not entirely rigorous way.

We are given that L1 contains L as a substring. Since we know L is regular, by Pumping Lemma, we can split L into xy^nz where we can n can be any integer and xy^nz will still be regular.

Since every string in L1 contains L as a substring, we can have a situation like this:

(w1)L(w2) where w1 and w2 are strings.

Even here, we can write L1 = (w1)xy^nz(w2) and pump n.

Therefore, if L is regular, then by Pumping Lemma, L1 is regular.

therefore, I) is true

Using similar logic, we can show II) is true

If we look at the options, if I and II are both true, the answer can only be E) I, II, III are true.

Thus, we would not need to evaluate III. Incidentally, I do not know how to prove or disprove that statement.

Can anyone help?

Your solution relys on the claim that because L1 can be pumped, it is regular.

The pumping lemma says that is a language is regular then it can be pumped. It does not say that a language that can be pumped has to be regular.

A simple counter example: Take any undecidable language L over {a,b}. Let LP = { uvc^n | uv is in L }. LP can be pumped, but is in no way regular.

G.

[blah321]

L1 is the set of words which have some word/words of L as a subset.
Let L = {a,b} - just 2 words. So, L is regular and context-free and recursive.
Let L1 = {a^nb^n,n>0}.
L1 is the set of words {ab,aabb,aaabbb,...} where each word has the word {a} as a subset.
Isn't this a counter-example to: (I) If L is regular, L1 is regular ?

Rojkumar said that 'you have to show the converse as well'. But do we have to ?
'L1={w|w contains some x belonging to L as a substring'}
This does not mean that Every word in L should be a substring of some word in L1. It is enough if Any word in L is a substring of all words in L1.
Also there is no restriction that the substring should be somewhere in the middle.