Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm stuck with this exercise from a course in formal languages that I am taking.

Could someone help me with this?

Big thanks!

For any w, define $w^R$ as

$\lambda ^R \text{ = $\lambda $}$

$(a.w)^R \text{ = } w^Ra\text{ }\left(a \in \Sigma , w \in \Sigma ^*\right)\text{ }$

Define $G^R$ as $G^R$ = (V,T,$P^R$,S) where $P^R$ such as

$A \to \alpha \in P \Leftrightarrow A \to \alpha ^R \in P^R$

Prove that L($G^R$) = $(L(G))^R$

(if necessary, assume (x.y) = $y^R$$x^R$ and $(w^R)^R$=w

share|cite|improve this question
I understand that $G$ is a grammar and $P$ is the set of productions, but it would really help if you would say stuff like that. Is $G$ guaranteed to be a regular grammar? A context-free grammar? Anyway, my suggestion is that you first show that $L(G^R)\subset(L(G))^R$ by induction on the length of an element of $L(G^R)$ and then $(L(G))^R\subset L(G^R)$ similarly. Does that help? Did you understand what $^R$ means here? – MJD May 1 '12 at 21:09
@mpm: Could you please either accept David's answer or explain why you're not satisfied with it? – Tara B May 7 '12 at 13:33
up vote 0 down vote accepted

Thanks for saying this is homework -- helps everybody maintain all-important academic integrity. Based on that, here are some hints...

Have you worked much with induction? Presumably you have, because that's what this problem is all about.

Notice how the reversal operator is defined inductively. Also notice how the teacher's first hint is stated inductively -- it says something about a string by working with the same property for some of its substrings, which are shorter.

So, try to work out how the induction goes for the proof. Presumably you have seen some proofs about grammars using induction -- how do they work?

What's the base case? What's the induction assertion, wherein you assume something true up to a point and and then show that it's also true for the next step up. Here's a hint on that for this problem -- you might be tempted to base the induction assertion on the terminal strings of the grammar, $L(G^R) \subseteq T^*$, but that probably won't work directly. Why? Look at the productions -- are the right-hand sides always terminal strings? Well, that's where the reversal happens.

Need more hints? Say how far you got and ask more questions.

@mpm -- Yes, induction on the length of derivations will work. Keep in mind, however, that derivations involve non-terminals as well as terminals.

Write down corresponding derivations in both $P$ and $P^R$ with $n+1$ steps, nicely lined up with each other, say with sequences $w_i$ and $z_i$ respectively. What does your induction assertion for $n$ say about the relationship between those two sequences? What form must $w_n$ and $w_{n+1}$ have and how do you get from one to the next? Likewise for $z_n$ and $z_{n+1}$.

Another hint here -- the instructor's first hint involves two strings: $(xy)^R=y^Rx^R$, and you say you are trying to set up the induction with two: $v$ and $w$. But you may need three, which you can prove from the instructor's hint or perhaps just assume. Also, what is the reversal of a single symbol $A$?.

share|cite|improve this answer
I am trying to prove inductively, on the number of derivation steps, that A->w for G <=> A->w^r for G^r. Assuming that the claim holds for <=n steps and w is the string produced in <=n steps, the inductive step may be of three forms: A->w->vw or A->w->wv or A->w->vwx. Is this strategy correct? Thanks! – marcos May 2 '12 at 1:42
@mpm See addendum to answer. – David Lewis May 2 '12 at 10:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.