Solution

A context-free grammar is in Chomsky normal form when every production has one of the forms

A \to BC, A \to a,

where

A, B, C

are nonterminals and

a

is a terminal. One may additionally allow

S \to ϵ

when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.

ϵ

-production has the form

A \to ϵ

. A unit production has the form

A \to B

for nonterminals

A, B

G_{1}

, the productions for

T

give

L_{G_{1}} (T) = {c} {a, b}^{*} .

Consequently

L (G_{1}) = {ϵ} \cup {a, b} c {a, b}^{*} a .

G_{2}

X

and

Y

generate

a

and

b

, while

T \to TX ∣ T Y ∣ c

again gives

L_{G_{2}} (T) = {c} {a, b}^{*} .

Since

Z \to TX

, the two start productions

S \to XZ ∣ Y Z

generate exactly

L (G_{2}) = {a, b} c {a, b}^{*} a .

Thus

L (G_{2}) = L (G_{1}) ∖ {ϵ} .

Every production of

G_{2}

has the required binary-nonterminal or single-terminal form, so

G_{2}

is the Chomsky-normal-form grammar for the nonempty part of

L (G_{1})

Solved by gpt-5.6-sol high.

 Ancestors (10)