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?

Printable View

- June 27th 2010, 05:04 PMApprentice123Context-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? - June 28th 2010, 12:26 PMApprentice123
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

- June 28th 2010, 03:37 PMundefined
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 - June 28th 2010, 05:41 PMApprentice123
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 ? - June 28th 2010, 07:42 PMundefined
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. - June 28th 2010, 08:57 PMApprentice123
Thanks. I think you're right

- June 29th 2010, 06:46 AMApprentice123
I found another language I do not understand

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

What "with balanced parentheses" ? - June 29th 2010, 07:21 AMundefined
() balanced

(()) balanced

()() balanced

(()()) balanced

(() not balanced

)( not balanced

(())) not balanced

potentially useful link. - June 29th 2010, 07:53 AMApprentice123
Then it is just that:

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

Correct ? - June 29th 2010, 09:00 AMundefined
- June 29th 2010, 09:15 AMApprentice123
S -> xS | yS | ()S | (S) | E

I had not noticed. Now I think that is correct. This right? - June 29th 2010, 09:35 AMundefined
- June 29th 2010, 10:12 AMApprentice123
Now I can

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

??? - June 29th 2010, 10:13 AMApprentice123
Now I can

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

??? - June 29th 2010, 10:29 AMundefined