# Thread: Context-free grammar

1. ## Context-free grammar

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?

2. 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

3. Originally Posted by 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?
1) The syntax of L1 = {w|w is palindrome in {a,b}^* , w=w^*} does not seem right. How can w = w^*? My guess is that one of the following is meant:

(1a) L1 = {w|w is palindrome in {a,b}^*}

Then I think your answer would be correct except that empty strings are not considered palindromes. So I would modify as follows:

S -> aSa | bSb | a | b

(1b) L1 = {w|u is palindrome in {a,b}^* , w=u^*}

Consider that every single character is a palindrome, for example "a" is a palindrome, and so is "b." So this is just all strings over {a,b}^*.

S -> Sa | Sb | E

(1c) L1 = {w*|w is palindrome in {a,b}^*}

This is equivalent to (1b).

2) With similar reasoning to above, I believe this language is all non-empty strings over {a,b}^*. So I get

S -> Sa | Sb | a | b

4. OK. Thank you
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 ?

5. Originally Posted by Apprentice123
OK. Thank you
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 ?
I'm not sure exactly what this means, but I guess it means regular expressions with an alphabet consisting of the single character x, such as x? , x* , x+ , x | x, etc. There isn't a whole lot of variety, and the most general regex is x*. So I would just write

S -> Sx | E

Maybe check with your book or notes to see if there is some other definition given though.

6. Thanks. I think you're right

7. I found another language I do not understand

L4 = {w|w is word of {x,y,(,)}^* with balanced parentheses}

What "with balanced parentheses" ?

8. Originally Posted by Apprentice123
I found another language I do not understand

L4 = {w|w is word of {x,y,(,)}^* with balanced parentheses}

What "with balanced parentheses" ?
() balanced
(()) balanced
()() balanced
(()()) balanced
(() not balanced
)( not balanced
(())) not balanced

9. Then it is just that:

S -> x | y | () | (S) | E

Correct ?

10. Originally Posted by Apprentice123
Then it is just that:

S -> x | y | () | (S) | E

Correct ?
This isn't correct because for example there is no way to get the string

x()

11. S -> xS | yS | ()S | (S) | E

I had not noticed. Now I think that is correct. This right?

12. Originally Posted by Apprentice123
S -> xS | yS | ()S | (S) | E

I had not noticed. Now I think that is correct. This right?
Hmmm how would you produce (())(()) ?

13. Now I can
S -> xS | yS | ()S | (S) | SS | E

???

14. Now I can
S -> xS | yS | ()S | (S) | SS | E

???

15. Originally Posted by Apprentice123
Now I can
S -> xS | yS | ()S | (S) | SS | E

???
I believe this is right; however, S -> ()S is unnecessary since you can always do

S => SS => (S)S => ()S

using just the other rules. So we have

S -> xS | yS | (S) | SS | E

Page 1 of 2 12 Last