#self_doubt#CFG

Question

Are these two grammars equal?

1->-------------------

S->X|epsilon

X->BBX|epsilon

B->a|b

2->------------

S->AAS|epsilon

A->a|b

Comments

yes both are equal

Answer 1

They are equivalent , both generating the same language.

Not sure about equal because

$2$) has right recursion on starting state S

but in

$1$) no recursion on initial state  (Assuming S as initial state in both the grammars)