Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 4G / c

Table of contents
- Solution c

Solution

The original grammar generates

L (G) = {a^{n} b c^{n} : n \geq 0},

because each use of

S \to A S c

adds one

a

on the left and one

c

on the right, and

S \to B \to b

terminates the derivation.

Introduce nonterminals

S_{0}, X, C

and use

S_{0} S X A C \to A X ∣ b, \to A X ∣ b, \to SC, \to a, \to c .

Every production is in Chomsky normal form. The production

X \to SC

completes one matched

a, c

pair, while either start-like symbol terminates with

b

, so the grammar generates exactly the same language. These productions are a valid $G_{Chom}$ .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version