retagged by
5,414 views
3 votes
3 votes
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 | ε
retagged by

4 Answers

5 votes
5 votes
S->aB->aaB->aa unsuccessful

backtrack 1 time

S->aAb->abAbb->ababb unsuccessful

backtrak

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

So, 2 backtracking required
edited by
1 votes
1 votes
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
1 votes
1 votes

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

1 votes
1 votes
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
Answer:

Related questions

0 votes
0 votes
0 answers
2
ahmed65956 asked Sep 27, 2023
583 views
Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1E- E+TE->TT->0|1|2...
2 votes
2 votes
1 answer
4
shekhar chauhan asked Jun 4, 2016
656 views
A >AA+/AA*/ais it eligible to be used by SR parse.If we apply SR parse on this grammar then what will be the order of activation Record in Stack