edited by
7,710 views
15 votes
15 votes
Consider the following Grammar :

$S \rightarrow ZZ$

$Z \rightarrow xZ|y$

Which of the following represents a handle in the generation of the string "xxxyxy" ?

A.  $ZxZ$

B.  $Zxy$

C.  $xZxy$

D.  $xZ$

Please explain a little about handles too I have a little doubt about it. And do explain the difference between viable prefix and Handle Please :)
edited by

4 Answers

Best answer
41 votes
41 votes

A right-sentential form is a sentential form that occurs in the rightmost derivation of some sentence.

String , handle

$xxxyxy$ , y

$xxxZxy$    , xZ 

$xxZxy$ , xZ

$xZxy$ , xZ

$Zxy$ , y

$ZxZ$ , xZ

$ZZ$ , ZZ

$S$

So Handles are y, xZ and ZZ. Hence option D is correct

Viable prefix : viable prefix of a right-sentential form is a prefix which does not extend beyond that form's handle.

The prefixes of right sentential forms that can appear on the stack of a shift reduce
parser are called viable prefixes.

Handle :  it's the sequence of symbols that resulted from the most recently expanded nonterminal.

 

Let's find out all viable prefixes in this question,

We'll parse $xxxyxy$

$.xxxyxy$

$x.xxyxy$

$xx.xyxy$

$xxx.yxy$

$xxxy.xy$

$xxxZ.xy$

$xxZ.xy$

$xZ.xy$

$Z.xy$

$Zx.y$

$Zxy.$

$ZxZ.$

$ZZ.$

$S.$

Let set of viable prefix be $L$,

$L = \left \{ x,xx,xxx,xxxy,xxxZ,xxZ,xZ,Z,Zx,Zxy,ZxZ,ZZ,S \right \}$

 

 

selected by
1 votes
1 votes

$Handles=\{y,xZ,ZZ\}$

$Viable\ prefixes=\{x,xx,xxx,xxxy,xxxZ,xxZ,xZ,Z,Zx,Zxy,ZxZ,ZZ\}$


$S$

$\underline{ZZ}$ : $VP=\{Z,ZZ\}$

$Z\underline{xZ}$ : $VP=\{Z,Zx,ZxZ\}$

$Zx\underline{y}$ : $VP=\{Z,Zx,Zxy\}$

$\underline{xZ}xy$ : $VP=\{x,xZ\}$

$x\underline{xZ}xy$ : $VP=\{x,xx,xxZ\}$

$xx\underline{xZ}xy$ : $VP=\{x,xx,xxx,xxxZ\}$

$xxx\underline{y}xy$ : $VP=\{x,xx,xxx,xxxy\}$

 

0 votes
0 votes
Answer is d.

When we reduce RHS to LHS of a production then RHS of the production is called handle.

If we've a production A -> xyz, then when we reduce xyz to A, So xyz is a handle here.

In this question, only xZ can be a handle
0 votes
0 votes
Answer is d.

When we reduce RHS to LHS of a production then RHS of the production is called handle.

If we've a production A -> xyz, then when we reduce xyz to A, So xyz is a handle here.

In this question, only xZ can be a handle

Related questions

2 votes
2 votes
3 answers
2
0 votes
0 votes
1 answer
3
spriti1991 asked Apr 4, 2015
1,107 views
https://gateoverflow.in/?qa=blob&qa_blobid=6419625116648850773