# MCQ IN COMPUTER SCIENCE & ENGINEERING

## COMPUTER SCIENCE AND ENGINEERING

### THEORY OF COMPUTATION

 Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:
 A program B SQL-query C XML document D All of the mentioned
Explanation:

Detailed explanation-1: -7. If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the structure of w. Explanation: A parse tree or concrete syntactic tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context free grammar.

Detailed explanation-2: -The root of the parse tree is that start symbol. It is the graphical representation of symbol that can be terminals or non-terminals. Parse tree follows the precedence of operators.

Detailed explanation-3: -Which of the following statements are correct for a concept called inherent ambiguity in CFL? Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

Detailed explanation-4: -Parikhâ€™s theorem [1] states that the Parikh image of any context-free language is semilinear. Since semilinear sets coincide with the Parikh images of regular languages, the theorem is equivalent to the statement that every context-free language has the same Parikh image as some regular language.

Detailed explanation-5: -Ambiguous grammar: A CFG is said to be ambiguous if there exists more than one derivation tree for the given input string i.e., more than one LeftMost Derivation Tree (LMDT) or RightMost Derivation Tree (RMDT).

There is 1 question to complete.