Question

If G is S→aS/a, then show L(G) = {a}+

Answer 1

If a CFG G = (V, Σ, R, S) includes the rule S → ε, then clearly G can generate

ε. But G could still generate ε even if it doesn’t include the rule S → ε. For

example, if G has rules S → XY , X → aY | ε, and Y → baX | ε, then the derivation

S ⇒ XY ⇒ εY ⇒ εε = ε shows that ε ∈ L(G), even though G doesn’t include

the rule S → ε. So it’s not sufficient to simply check if G includes the rule S → ε to

determine if ε ∈ L(G).

But if we have a CFG G′ = (V

′

, Σ, R′

, S′) that is in Chomsky normal form, then G′

generates ε if and only if S

′ → ε is a rule in G′

. Thus, we first convert the CFG G

into an equivalent CFG G′ = (V

′

, Σ, R′

, S′) in Chomsky normal form. If S

′ → ε is

a rule in G′

, then clearly G′ generates ε, so G also generates ε since L(G) = L(G′).

Since G′

is in Chomsky normal form, the only possible ε-rule in G′

is S

′ → ε, so the

only way we can have ε ∈ L(G′) is if G′

includes the rule S

′ → ε in R. Hence