3 votes 3 votes Consider the following CFG : $S \rightarrow AB$ $A \rightarrow BC \mid a$ $B \rightarrow CC \mid b$ $C \rightarrow a \mid AB$ The Rank of Variable $A$ is: $2$ $3$ $4$ not possible to define Theory of Computation tbb-toc-1 + – Bikram asked Nov 26, 2016 • edited Aug 20, 2019 by Counsellor Bikram 948 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Pranav Kant Gaur commented Dec 29, 2016 reply Follow Share While developing the graph for a given grammer(to determine rank of its non-terminals), do we also include terminals? I mean, for example in the graph for given grammer, will there be edges like A->a, B->b, C->a also? Actually, I am not able to find authentic definition of rank of a non-terminal in a grammer, hence the question. 1 votes 1 votes vijaycs commented Dec 29, 2016 reply Follow Share Rank of variable A means maximum height of a terminal from node A... A / \ B C / \ / \ C C . . Keep going down ... here we can get a parse tree of infinite height .. right .. ?? 14 votes 14 votes Pranav Kant Gaur commented Dec 29, 2016 reply Follow Share Thanks...it is clear to me now!! 1 votes 1 votes Wanted commented Jan 22, 2017 reply Follow Share @vijaycs here we are getting end of tree in some transition....so that height we will not consider? 0 votes 0 votes KUSHAGRA गुप्ता commented Jan 3, 2020 reply Follow Share Cycle present 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes if we make a precedence graph for this grammar, there is a loop between A and C, hence we can't conclude the rank of A. Hence (D) is correct answer! Vijay Thakur answered Jan 29, 2017 • selected Jan 29, 2017 by Bikram Vijay Thakur comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Abhisek Tiwari 4 commented Nov 5, 2018 reply Follow Share if option have infinity also then ans will be infinity?? 0 votes 0 votes Gate Fever commented Nov 5, 2018 reply Follow Share YES ,I THINK SO!! 0 votes 0 votes Amoljadhav commented Nov 6, 2023 reply Follow Share will i know what is exact defination of rank of nonterminal in the grammer 0 votes 0 votes Please log in or register to add a comment.