2011 Semester b, moad a - Q6

2011 Semester b, moad a - Q6

yuval (guest) 10 Jul 2012 08:24

Hi, we don't understand the exact definition of a symetric gremmer.
Is the following gremmer also symetric?
s- > A | B
A-> 111
B-> 22 | A
if this is symetric gremmer, the lanugange it creates is not symetric so answer A (which is marked as the correct one) is disproved.
What are we missing in the definition?
Thank you.

Netanel (guest) 10 Jul 2012 08:32

But it is a symmetric grammar, and it's language is: L={111,22}, which is symmetric according to the definition.

yuval (guest) 10 Jul 2012 10:00

sorry i didn't copy the grammar correctly:
S -> AB | A
A-> 111
B-> 22

here you can create 111 and 11122, the languange is not symetric but the grammar (as we understand it)

Netanel (guest) 10 Jul 2012 12:01

But this is not a symmetric grammar.
The rule: S -> AB is not symmetric. AB != BA

Matan (guest) 12 Jul 2012 11:28

What about
S => BB
B => b | A
A => a | Aa
?

It is not in CNF though, but it doesn't say you have to use CNF in the question, and this grammar generates the word baaaaaaaaaaa (Which is not symmetric, but it does express my current feelings).

guest (guest) 12 Jul 2012 12:44

I also was not sure about the definition given in this question, but if Netanel is right - then the "Aa" in rule A also makes your grammar asymmetric, meaning it should be: AaA or aAa and so on.

Matan (guest) 12 Jul 2012 13:47

It can also be just AaA or you can erase this rule and still generate ba.

guest (guest) 12 Jul 2012 14:05

yes, but then you can also generate "ab", so L(G)={ab, ba} and Reverse(L(G))={ba, ab} => L(G)=Reverse(L(G)) => symmetric language.

Matan (guest) 12 Jul 2012 16:56

Thanks!

yz101 (guest) 12 Jul 2012 15:34

I think that the question was not well put. When written "A->w" with a capital 'A' and a regular 'w' it implies by convention that 'w' means a terminal and not a variable. In which case the rule mentioned does not apply for rules of the form A->AB where 'A' and 'B' are variables.

סטודנט (guest) 14 Jul 2012 16:59

למה תשובה ב אינה נכונה?
כלומר למה לא לכל שפה סימטרית קיים דקדוק חסר הקשר סמטרי שמייצר אותה?
לא הצלחתי למצוא דוגמה נגדית.
למישהו יש רעיון?

stp 14 Jul 2012 17:24

i guess that there are symmetric languages which are not context free at all so you can't generate them using CFG
like
$L = \{ a^n b^n a^n | n \in N \}$