Virtual Labs

Derivation of a string from a Context-Free Grammar

What is the primary difference between leftmost and rightmost derivations?

a: Leftmost uses more production rules Explanation

Explanation

b: Leftmost always expands the leftmost non-terminal first Explanation

Explanation

c: Rightmost generates different strings Explanation

Explanation

d: Rightmost is faster to compute Explanation

Explanation

In a derivation, what determines which production rule should be applied to a selected nonterminal?

a: The rule must be applied in alphabetical order Explanation

Explanation

b: The choice depends on the target string being derived Explanation

Explanation

c: Always apply the first rule listed in the grammar Explanation

Explanation

d: Rules are applied randomly Explanation

Explanation

What information does a complete derivation sequence provide?

a: Only the final string Explanation

Explanation

b: Only the production rules used Explanation

Explanation

c: The step-by-step transformation from start symbol to target string Explanation

Explanation

d: The grammar's complexity measure Explanation

Explanation

For the grammar S → (S) | SS | ε, what is the correct leftmost derivation sequence to produce the string '()()'?

a: S → SS → (S)S → ()S → ()(S) → ()() Explanation

Explanation

b: S → (S) → ()() → ()() Explanation

Explanation

c: S → SS → ()() Explanation

Explanation

d: S → ()() directly Explanation

Explanation

When deriving '(())', which production rule should be applied first to the start symbol S?

a: S → SS Explanation

Explanation

b: S → (S) Explanation

Explanation

c: S → ε Explanation

Explanation

d: None of the above Explanation

Explanation

When is a derivation considered successfully completed?

a: When all symbols are terminals Explanation

Explanation

b: When no more rules can be applied Explanation

Explanation

c: When the derived string matches the target string and contains only terminals Explanation

Explanation

d: When the derivation reaches a fixed length Explanation

Explanation

Consider the grammar E → E + T | T; T → T * F | F; F → (E) | id. For the string 'id + id * id', which parse tree correctly represents the unambiguous parse (respecting operator precedence)?

a: E[E[T[F[id]]] + T[T[F[id]] * F[id]]] Explanation

Explanation

b: E[E[E[T[F[id]]] + T[F[id]]] * F[id]] Explanation

Explanation

c: Both structures are valid Explanation

Explanation

d: Neither structure is valid Explanation

Explanation

For the grammar S → aSb | ab, what is the minimum number of derivation steps needed to generate 'aaabbb'?

a: 2 steps Explanation

Explanation

b: 3 steps Explanation

Explanation

c: 4 steps Explanation

Explanation

d: 5 steps Explanation

Explanation

Why can an ambiguous grammar such as E → E + E | E * E | id be problematic in practical applications?

a: It generates incorrect strings Explanation

Explanation

b: It cannot generate any valid expressions Explanation

Explanation

c: Multiple parse trees can lead to different semantic interpretations Explanation

Explanation

d: It violates formal grammar rules Explanation

Explanation