1
$\begingroup$

I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $

If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where
$ V $ = Set of Variables or Non-Terminal Symbols
$ \Sigma $ = Set of Terminal Symbols
$ \delta $ = Set of Production Rules
$ S $ = Start Symbol

By def. $$ G^R = \langle V \ ,\ \Sigma \ ,\ \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \}\ ,\ S \rangle $$

$$ G^* = \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\ \delta \ \cup \ \{S' \rightarrow S'S \ |\ \lambda\} \ , \ S' \rangle $$

Then I tried the following

$$ (G^R)^*= \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\ \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \} \ \cup \ \{S' \rightarrow S'S \ |\ \lambda\} \ , \ S' \rangle $$ and $$ (G^*)^R = \langle V \ \cup \ \{S'\} \ , \ \Sigma \ ,\ \{X \rightarrow \ u^R | \ (X \rightarrow u) \ \epsilon \ \delta \} \ \cup \ \{S' \rightarrow S S' \ |\ \lambda\} \ , \ S' \rangle $$

I do not know how to continue, I haven't found any counterexample

$\endgroup$
  • 1
    $\begingroup$ Does the claim hold for languages, with the usual definitions? Can you connect the two? $\endgroup$ – Yuval Filmus Apr 1 '18 at 21:21
  • $\begingroup$ Yes. I have the demonstration with languages $(L^R)^* = (L^*)^R$ I can say that if a grammar $G$ generates a language $L$, with proof that $(L^ R)^* = (L^*)^R then (G^R)^* = (G^*)^R$ ? $\endgroup$ – Jordi Gil Apr 1 '18 at 22:26
  • 1
    $\begingroup$ What is the effect of the two operations on the language generated by the grammar? $\endgroup$ – Yuval Filmus Apr 2 '18 at 5:01
  • $\begingroup$ I don't understand what you mean by what effect they have on the generated languages. The Kleen Star operation generates all the words of the language and the reverse operation the reverse of these. In a grammar, the star operation adds a new symbol to generate the concatenation of 0 or more words of L and the reverse operation applies the reverse to the right parts of the rules. $\endgroup$ – Jordi Gil Apr 2 '18 at 13:08
  • 1
    $\begingroup$ The real question is whether you're interested in equality of grammars or in equality of the languages they generate. The latter is discussed in my previous comment. If the former, then you first have to define when two grammars are equal; once you do, take any grammar, compute both sides of the equation, and see whether they're equal. If they aren't (which will be the case), then you have found a counterexample. $\endgroup$ – Yuval Filmus Apr 2 '18 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.