Take the 2-minute tour ×
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.

The BNF is defined as followed:

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

The sentence is:

aaAbBb

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?

Thanks,
Chan

share|improve this question
    
Does this go here, or on cstheory.stackexchange.com? –  Orbling Feb 18 '11 at 2:40
    
@Orbling It's not at a high enough level to belong cstheory, but it doesn't seem correct for this site either. –  Brandon Carter Feb 18 '11 at 2:42
    
@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!) –  Orbling Feb 18 '11 at 2:46
3  
@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. –  Chan Feb 18 '11 at 4:58
1  
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. –  Ken Li Mar 13 '12 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.

share|improve this answer

Your Answer

 
discard

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.