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
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.
() balanced
(()) balanced
()() balanced
(()()) balanced
(() not balanced
)( not balanced
(())) not balanced
potentially useful link.