If |w|>=2^h, then its parse tree’s height is at least _____(a) h(b) h+1(c) h-1(d) 2^hI have been asked this question by my school teacher while I was bunking the class.Origin of the question is Inferences to Trees, Trees to Derivations topic in section Context Free Grammars and Languages of Automata Theory

If |w|>=2^h, then its parse tree’s height is at least _____(a) h(b)

1.	If \|w\|>=2^h, then its parse tree’s height is at least _____(a) h(b) h+1(c) h-1(d) 2^hI have been asked this question by my school teacher while I was bunking the class.Origin of the question is Inferences to Trees, Trees to Derivations topic in section Context Free Grammars and Languages of Automata Theory
Answer» Right choice is (b) H+1 The explanation is: It is the basic IMPLICATION of Parse tree THEOREM (assuming CNF). If the height of the parse tree is h, then \|w\| <=2^h-1.

Discussion

No Comment Found

Related InterviewSolutions

The _______ table is created by YACC.(a) LALR parsing(b) LL parsing(c) GLR parsing(d) None of the mentionedThe question was posed to me during an interview.This intriguing question originated from YACCParser Generator topic in section Context Free Grammars and Languages of Automata Theory
Which of the following parsers do not relate to Bottom up parsing?(a) LL parser(b) Recursive descent parser(c) Earley parsers(d) All of the mentionedThis question was addressed to me in an interview.Question is taken from Applications in portion Context Free Grammars and Languages of Automata Theory
Which of the following statement is false in context of tree terminology?(a) Root with no children is called a leaf(b) A node can have three children(c) Root has no parent(d) Trees are collection of nodes, with a parent child relationshipI got this question during an interview for a job.This interesting question is from Construction and Yield of a Parse Tree in section Context Free Grammars and Languages of Automata Theory
A language that admits only ambiguous grammar:(a) Inherent Ambiguous language(b) Inherent Unambiguous language(c) Context free language(d) Context Sensitive languageThis question was posed to me during an online interview.This key question is from Ambiguous Grammar in section Context Free Grammars and Languages of Automata Theory
LALR in LALR parser stands for:(a) Left aligned left right parser(b) Look ahead left to right parser(c) Language Argument left to right parser(d) None of the mentionedThis question was addressed to me in an internship interview.My question is from Applications topic in portion Context Free Grammars and Languages of Automata Theory
A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:B->aCB->a(a) Ambiguous(b) Regular(c) Non Regular(d) None of the mentionedThis question was posed to me during a job interview.This intriguing question comes from Sentential Forms topic in portion Context Free Grammars and Languages of Automata Theory
troff and nroff are _________ in Unix.(a) functions(b) typesetting tools(c) System sofwares(d) None of the mentionedThis question was addressed to me in an online interview.Question is taken from Markup Languages topic in section Context Free Grammars and Languages of Automata Theory
YACC is a computer program for ______ operation system.(a) Windows(b) DOS(c) Unix(d) openSUSEI got this question in an interview for internship.I would like to ask this question from YACCParser Generator topic in division Context Free Grammars and Languages of Automata Theory
Which of the following is false for B programming language?(a) Typeless(b) Influenced by PL/I(c) Designed by Dennis Ritchie(d) None of the mentionedThe question was posed to me in final exam.My question is from YACCParser Generator in section Context Free Grammars and Languages of Automata Theory
State true or false:Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.(a) Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.(b) true(c) falseThis question was addressed to me in an interview for internship.Asked question is from The Language of a Grammar, Inferences and Ambiguity topic in division Context Free Grammars and Languages of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment