Virtual Labs

Derivation of a string from a Context-Free Grammar

What is a parse tree in the context of context-free grammars?

a: A linear sequence of production rules Explanation

Explanation

b: A tree structure showing how a string is derived from the start symbol Explanation

Explanation

c: A diagram of the grammar's non-terminals Explanation

Explanation

d: A list of all possible strings in the language Explanation

Explanation

In a grammar for balanced parentheses, what does the production rule S → (S) represent?

a: Creating nested parentheses around existing content Explanation

Explanation

b: Removing parentheses from a string Explanation

Explanation

c: Counting the number of parentheses Explanation

Explanation

d: Checking if parentheses are balanced Explanation

Explanation

What is the difference between terminal and nonterminal symbols in a CFG?

a: Terminals are at the top, non-terminals are at the bottom Explanation

Explanation

b: Terminals cannot be expanded further, non-terminals can be replaced using production rules Explanation

Explanation

c: Terminals are letters, non-terminals are numbers Explanation

Explanation

d: There is no difference Explanation

Explanation

For the grammar S → aSb | ab, what string would be generated after applying the derivation S → aSb → aaSbb → aaabbb?

a: aabb Explanation

Explanation

b: aaabbb Explanation

Explanation

c: abab Explanation

Explanation

d: ababab Explanation

Explanation

In the grammar E → E + T | T; T → T * F | F; F → (E) | id, what precedence relationship does the grammar enforce?

a: All operations have equal precedence Explanation

Explanation

b: Multiplication has higher precedence than addition Explanation

Explanation

c: Addition has higher precedence than multiplication Explanation

Explanation

d: Parentheses are not allowed Explanation

Explanation

When building a parse tree interactively, what determines which production rule to choose for a selected node?

a: The system automatically chooses the best rule Explanation

Explanation

b: Rules are applied in alphabetical order Explanation

Explanation

c: The user must select the appropriate rule based on the target string Explanation

Explanation

d: Rules are applied randomly Explanation

Explanation

For the balanced parentheses grammar S → (S) | SS | ε, to generate the string '(())()', which rule should be applied first to the start symbol?

a: S → (S) Explanation

Explanation

b: S → SS Explanation

Explanation

c: S → ε Explanation

Explanation

d: Any rule can be applied first Explanation

Explanation

In the string generation grammar S → aSb | ab, what is the relationship between the number of 'a's and 'b's in any generated string?

a: There are always more 'a's than 'b's Explanation

Explanation

b: There are always more 'b's than 'a's Explanation

Explanation

c: The number of 'a's always equals the number of 'b's Explanation

Explanation

d: The relationship varies depending on the derivation Explanation

Explanation

What happens if you try to build a parse tree for a string that is not in the language generated by the grammar?

a: The system will automatically fix the grammar Explanation

Explanation

b: A partial tree will be created Explanation

Explanation

c: You will not be able to complete the derivation to match the target string Explanation

Explanation

d: The grammar will be marked as incorrect Explanation

Explanation