The BNF is defined as followed:

S -> aAb | bBA 
A -> ab | aAB
B -> bB | b

The sentence is:


And this is the parse tree: enter image description here

Phrases: aaAbBb, aAbB, bB
Simple Phrases: bB
Handle: ?

From the book, handle is defined as followed: B is the handle of the right sentential from y = aBw if and only if:
$S ->_{rm} \cdot aAw ->_{rm} aBw$

So in my case, what's the handle? Any idea?


  • $\begingroup$ Does this go here, or on cstheory.stackexchange.com? $\endgroup$
    – Orbling
    Feb 18, 2011 at 2:40
  • $\begingroup$ @Orbling It's not at a high enough level to belong cstheory, but it doesn't seem correct for this site either. $\endgroup$ Feb 18, 2011 at 2:42
  • $\begingroup$ @Brandon Carter: I don't like there being a level requirement on the sites, unless they are specific overflow in the upwards direction. If it is not suitable for cstheory, then perhaps SO or maybe programmers? Problem is, it uses MathJaX, which only works here... :-/ (for some ungodly reason!) $\endgroup$
    – Orbling
    Feb 18, 2011 at 2:46
  • 3
    $\begingroup$ @Yuval Filmus: I really hope cstheory will open a section for newbies, since the CS theory is not easy to be self-taught, plus , why limits it to only graduate level. $\endgroup$
    – Chan
    Feb 18, 2011 at 4:58
  • 1
    $\begingroup$ I have cross-posted this question onto cs.stackexchange.com/questions/290/… which is probably a better SE for these types of questions, and as an effort to seed the site which is currently in private beta with useful content. $\endgroup$
    – Ken Li
    Mar 13, 2012 at 6:59

1 Answer 1


The rightmost derivation of $aaAbBb$ is

$$\underline{S}\Rightarrow\color{red}{a\underline{A}b}\Rightarrow a\color{green}{aA\underline{B}}b\Rightarrow aaA\color{blue}{bB}b\;.$$

The underlined non-terminals are the ones replaced in the next step of the derivation; each is replaced by the colored substring in the next word of the derivation.

The last production that was employed to reach $aaAbBb$ is $B\to bB$, so $bB$ is the handle of $aaAbBb$.

You may find this PDF to be of some use.


Your Answer

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

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