Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?
| Grammar | Productions |
|---|---|
| A | S → Ab aS → aA A → a |
| B | S → Ab A → Sa A → a |
| C | S → AS S → aA A → a |
| D | S → Ab S → aA A → a |
| E | S → Sb A → Aa A → ε |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. C, D Only
Explanation
A has the rule aS → aA, whose left side has more than one symbol, so it is context-sensitive, not context-free. E (S → Sb, A → Aa, A → ε) is entirely left-linear, so it is a regular grammar. C has S → AS (two non-terminals on the right) and D mixes a left-linear rule S → Ab with a right-linear rule S → aA, so neither is a regular grammar; both are only context-free. (B is also context-free, but no option pairs it correctly, so C, D is the answer.)More Theory of Computation and Compilers questions
- Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a d…
- Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:State a b c →* q0 q1 q0 q0 q…
- Match List I with List IIList I List II A. Type 3 Grammar I. V → (V ∪ Σ)* B. Type 2 Grammar II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* C.…
- Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powe…
- What are the various LEADERS (leading statements) for the TAC given in the passage?
- Which of the following is the optimized version of the TAC given in the passage?