Which one of the following is not a Greibach Normal Form grammar? (i) S → a |…

2012

Which one of the following is not a Greibach Normal Form grammar?

(i)   S → a | bA | aA | bB
      A → a
      B → b
(ii)  S → a | aA | AB
      A → a
      B → b
(iii) S → a | A | aA
      A → a

Answer: C. (ii) and (iii) — ConceptA context-free grammar is in Greibach Normal Form (GNF) when every production has the shape A → aα, where a is a single terminal symbol and α is a…

  1. A.

    (i) and (ii)

  2. B.

    (i) and (iii)

  3. C.

    (ii) and (iii)

  4. D.

    (i), (ii) and (iii)

Attempted by 18 students.

Show answer & explanation

Correct answer: C

Concept

A context-free grammar is in Greibach Normal Form (GNF) when every production has the shape A → aα, where a is a single terminal symbol and α is a possibly empty string of variables. The first symbol of every right-hand side must therefore be a terminal, and every symbol after it must be a variable. A right-hand side that begins with a variable, or that consists of a lone variable (a unit production), does not fit this shape.

Application

Apply the shape test to each grammar in turn.

  1. Grammar (i): the right-hand sides are a, bA, aA and bB for S, a for A, and b for B. Each one begins with a terminal (a or b) and carries at most one variable after it, so every production matches A → aα. Grammar (i) is in Greibach Normal Form.

  2. Grammar (ii): S → a and S → aA match the shape, and A → a and B → b match it too, but S → AB begins with the variable A, so its right-hand side has no leading terminal. Grammar (ii) is not in Greibach Normal Form.

  3. Grammar (iii): S → a and S → aA match the shape, and A → a matches it too, but S → A is a unit production whose whole right-hand side is a single variable, again with no leading terminal. Grammar (iii) is not in Greibach Normal Form.

Cross-check

Scan only the first symbol of every right-hand side; a grammar sits in Greibach Normal Form when that whole list is made of terminals.

Grammar

Right-hand sides

First symbol of each

(i)

a, bA, aA, bB, a, b

a, b, a, b, a, b

(ii)

a, aA, AB, a, b

a, a, A, a, b

(iii)

a, A, aA, a

a, A, a, a

The first-symbol list carries a variable for grammar (ii) and for grammar (iii), so the grammars that are not in Greibach Normal Form are (ii) and (iii).

Contrast

Do not confuse this with Chomsky Normal Form, whose productions look like A → BC or A → a. A grammar can sit in one of the two normal forms and stay outside the other, so the test has to be run against the definition being asked about.

Explore the full course: Mppsc Assistant Professor Computer Science Paper 2

Loading lesson…