Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 4F / d

Table of contents
- Solution d

Solution

Take

G = ({a, b, c}, {S, A, B}, {S \to A B, A \to a, B \to b}, S)

and

G^{'} = ({a, b, c}, {T}, {T \to c}, T) .

These are variable based and have disjoint variable sets. They satisfy

L (G) L (G^{'}) = {ab c} .

In

H^{reg}

, however, both terminal productions of

G

are replaced:

A \to a T, B \to b T .

Consequently its only terminal derivation is

S \Rightarrow A B \Rightarrow a TB \Rightarrow a T b T \Rightarrow a c b c,

so

L (H^{reg}) = {a c b c} \neq = {ab c} .

This realizes the failure of the regular concatenation construction for a nonregular grammar: two different terminal productions introduce two copies of

T

.

 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