12 replies to this topic

[Apprentice123]

Develop context-free grammars that generate languages:

L1 = {w|w is palindrome in {a,b}^* , w=w^*}
L2 = {ww^* | w is word of {a,b}^*}


My attempt
1)
S -> aSa | bSb | E | a | b
E is empty
Correct ?

2) I could not. Any tips?

[abzero]

I must admit, I'm not sure of your syntax in that definiation. What does the ^ symbol mean in your L2 def?

[Apprentice123]

Means that it is elevated to *
Means that it accepts the empty word

[abzero]

your using it like a superscript?

If I read it rightly (which I may not be) it, saying that you must have at least one word, followed by Zero or more words. You solution for L1 seems to be correct.

[Apprentice123]

Yeah is a superscript.

2) I think is (ww)^* which means that it is a word that read from the early to mid is the same when read to the end of the half. But I can not generate the language

[abzero]

again, it's been too long since i've looked at that syntax...Anyway if what it means that w is a word, and the language is ww*..
So these are valid:

aa
aaa
abab
ababab
abbabbabb
aabaab
etc...

If you think about it, what that is saying is that the original pattern matched needs to be re-matched. Or the second part of the grammer depends on the context of the first. Do you think in a context free grammar you'd be able to match it?

But if I'd mis-interrupted the question I may be wrong.

[bobdark]

1) take out S->a,S->b

2) of course you couldn't find the grammar - its not a context free language.
Theres a proof:
Pumping lemma for context free grammars:
If a language L is context-free, then there exists some integer p > 0 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as
s = uvxyz with substrings u, v, x, y and z, such that |vxy| ≤ p, |vy| ≥ 1, and
uv nxy nz is in L for every integer n ≥ 0.now lets assume that L2 is indeed context free, thus such p exists for L2. Consider the word: a^(p)b^(p)a^(p)b^(p), i.e. w=p times 'a' then p times 'b', and we're talking about word t=ww.
now according to the lemma, t can be broken into substrings t=uvxyz, such that |vxy|<=p and |vy|>0.
lets break it into cases:
1) vxy falls in the first p a's - then if we take any n=3, uv^(n)xy^(n)z=a^(p+4)b^(p)a^(p)b^(p) and it is not of form ww, thus not in L2.

2) lets treat it as a general case, if vxy falls in the first w from ww, we can take any n>1, and uv^nxy^nz wont be in L2, because we "pump" only the first w, thus breaking the symmetry.

3) same goes if vxy falls in the second w.

4)last case, vxy falls in the middle, i.e. under some part of first w(lets call it w1) and under some part of w2. Notice though, that in this case the part of w1 that vxy falls under, will consist of b's only because there are p b's in latter part of w1. In the same way, the part of w2 that vxy falls under will consist only of a's. Thus for any n>1 we will increase number of b's in w1 and number of a's in w2, thus again breaking the symmetry, and resulting in uv^nxy^nz not in L2.

pretty long but i hope i convinced you.

[Apprentice123]

abzero said:

again, it's been too long since i've looked at that syntax...Anyway if what it means that w is a word, and the language is ww*..
So these are valid:

aa
aaa
abab
ababab
abbabbabb
aabaab
etc...

If you think about it, what that is saying is that the original pattern matched needs to be re-matched. Or the second part of the grammer depends on the context of the first. Do you think in a context free grammar you'd be able to match it?

But if I'd mis-interrupted the question I may be wrong.

I think the second part of the grammar (the second w) equals the first part (the first w) or empty
Is not it?

[abzero]

@bobdark 's got it (cheers). The point of the question is to show you that some things can't be parsed. Do you see why you can't create a grammar for it?

[Apprentice123]

I'm not managing to create the grammar just do not see why.

[bobdark]

Apprentice123 said:

I'm not managing to create the grammar just do not see why.

because such doesn't exist :/

[Apprentice123]

Thanks. And the language:

L3 = {w | w regular expression is about {x} }

Which means: it is about regular expression {x} ? I can generation a context-free grammar ?