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 '11 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$ – Brandon Carter Feb 18 '11 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 '11 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 '11 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 '12 at 6:59

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.