Question

Consider the following grammar.  How many back tracks are required to generate the string aab from the above grammar?

S → aB | aAb

A → bAb | a

B → aB | ε

Comments

All the previous year Gate questions are already availble please search it before posting again

---

i saw it,but not clarified

plzzz help

---

2 backtracks

Answer 1

S->aB->aaB->aa unsuccessful

backtrack 1 time

S->aAb->abAbb->ababb unsuccessful

backtrak

S->aAb->aab //successful , no backtrack

So, 2 backtracking required

Comments

could you plzzz explain in detail

---

Why don't we consider the production B-> ὲ ?? can anyone please explain this?

---

I am getting 3 as no of backtracing.

1.  S->aB->aaB->aa unsuccessful

2. S->aB-> aὲ-> a unsuccessful

3. S->aAb->abAbb->ababb unsuccessful

4. S->aAb->aab //successful , no backtrack

Please explain

Answer 2

No of Backtrack=2.

Backtrack is nothing but no of attempts requires to derive particular string by top down parser.

S-> aaB-> aa

S-> aAb-> abAbb -> ababb

S -> aAb -> abb

Comments

But ans given is 2 :(

Given Solution :

S-> aB-> abb

S-> aAb-> abAbb -> ababb

S -> aAb -> abb

---

Isn't the explanation itself says that no of backtrack is 3

Answer 3

Backtrack is nothing but how many tries(attempts) have done inorder to generate the given string from Start symbol by the Top down parser.

Intially,from start symbol S first production is selected follwed by production of B but with the first production selected we couldn't generate the given string aab

S->aB->aaB->aa // Unsuccessful 

Backtrack

Next it will select second production from start symbol S and first production from A

S->aAb->abAbb->ababb //Unsuccessful

Backtrack

Now it will select Second production from start symbol S and second produciton from A

S->aAb->aab //successful , no backtrack

Thus 2,backtracks are required to generate string aab

Comments

AFAIK Start with Start Symbol Replace all Variables with terminals if the required string is not obtained we backtrack,

Here Start with start symbol S select first production there on try to replace all the variables.

---

Are these not the possibilities, other than 2 possibilities mentioned in the answer?

S->aB->a              // Unsuccessful

S->aB->aaB->aaa // Unsuccessful

Please explain.

---

Why is it not considering other option of B? i.e B->e
For S, it has two options: S->aB and S->aAb. If it chooses S->aB, it has two other options: B->aB and B->e. Let it choose B->aB => S->aB->aaB. Again 2 options: S->aB->aaaB (backtrack=1)  S->aB->aa (backtrack =2). So it backtracts S->aB.

Now it chooses, S->aAb. Two other options: A->bAb and A->a. i.e S->aAb->abAbb (backtrack=3). S->aAb->aab(success).

So, isn't it no.of backtracks =3?

Answer 4

i think it depends...

let string to be genreted  be "aab".

if first production taken is S->aAb then deterministically it can take A->a in next step...and hence '0' backtracks

but if first production taken is S->aB then it will take B->aB in next step and it will find that it can not go further to generate "aab" and hence it will take '2' backtrack to come back to S and start with production S->aAb

Comments

you mean backtrack should always start from the start symbol.

first we have to finish the possibility of start symbol then move to intermediate symbol.is there somewhere written rule about this?

---

one backtrack will also be there when we choose bAb for A

---

No, i havent said that it will always start from start symbol, but in this question see below,

S->aB then B->aB, now no production of B can satisfy further generation and it will backtrack to previous B in which also no remaining production(B->ε) will satisfy therefore it will finally backtrack to S.

---

@Akriti Sood...it will not choose A->bAb

it will deterministically choose A->a, since..

in string "aab" it has already seen first 'a' and taken move(S->aAb) now it is looking at second 'a' therfore it has no choice other than A->a..