Thread: 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) 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

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

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 ?

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.

Thanks. I think you're right

I found another language I do not understand

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

What "with balanced parentheses" ?

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

potentially useful link.

Then it is just that:

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

Correct ?

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()

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


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

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 (())(()) ?

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

???

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

???

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