Q41MSQ

Choose the correct alternatives (more than one may be correct ) and write the corresponding letters only: Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statement is/are true?

🚀 Solve in Practice Mode

📖 Explanation

The $GOTO$ table depends solely on the $LR(0)$ state machine, which is identical for both SLR(1) and LALR(1) parsers, meaning statement A is false. Since both parsers share the same $LR(0)$ states and transitions, their shift entries are identical, making statement B true. SLR(1) bases reduction decisions on $FOLLOW(A)$ , while LALR(1) uses specific lookahead sets, leading to different reduce entries (C). Consequently, because the reduce entries differ, the distribution of error entries must also differ, making statement D true.

[CORRECT_OPTION: B, C, D]

Q42MSQ

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal A in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

🚀 Solve in Practice Mode

📖 Explanation

$RFOLLOW(A)$ considers only rightmost derivations; since any sentential form $S \Rightarrow^* \alpha A a \beta$ can be generated by a rightmost derivation, $RFOLLOW(A)$ is identical to $FOLLOW(A)$ . Conversely, $LFOLLOW(A)$ is defined using only leftmost derivations ( $S \Rightarrow_{lm}^* \alpha A a \beta$ ), which constitute a subset of all possible derivations. Because terminals $a$ might only appear after $A$ in non-leftmost derivations, $LFOLLOW(A)$ is a subset of $FOLLOW(A)$ and may be strictly smaller. Thus, $FOLLOW(A)$ and $LFOLLOW(A)$ may differ, while $FOLLOW(A)$ and $RFOLLOW(A)$ are always the same.

[CORRECT_OPTION: A, B]

Q43MCQ

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If G is a context free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is in Chomsky normal form?

🚀 Solve in Practice Mode

📖 Explanation

A derivation of a string $w$ of length $l$ in Chomsky Normal Form (CNF) can be represented as a binary tree.
The derivation requires $l$ production steps of the form $A \rightarrow a$ to generate the $l$ terminal symbols at the leaves.
The remaining internal nodes in the tree represent production steps of the form $A \rightarrow BC$ .
A binary tree with $l$ leaf nodes must have exactly $l-1$ internal nodes.
Therefore, the total number of derivation steps is the sum of terminal productions and internal node expansions: $l + (l - 1) = 2l - 1$ .

Q44MCQ

A context-free grammar is ambiguous if:

🚀 Solve in Practice Mode

📖 Explanation

A context-free grammar $G$ is defined as ambiguous if there exists at least one string $w \in L(G)$ that has more than one distinct parse tree. This implies the string $w$ can be derived in at least two different ways, typically represented by distinct leftmost derivations. Option A refers to grammar simplification, while option C describes valid, standard production rules. accurately captures the formal definition of ambiguity in formal language theory.