Re: On the General Construction for Kleene star in Context-Free Language

On Feb 24, 2:16 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
wrote:
Federico Magallanez wrote:
I have a first edition of 'Elements of the Theory of Computation' by
Lewis and Papadimitriou, which is published in early 1980s. In this
edition, the author said that we can construct Kleene star operation
in context-free language (CFL) in this way.

Let G = (V, T, P, S) be a CFG where S is a starting symbol. Then
adding another rule that 'S -> SS | \epsilon' generates Kleene closure
of the language that G generates.

Is there anyone who knows the counterexample?

Here's one. Let G = (S, {a,b}, P, S) where P contains the single rule:

S -> \epsilon | aSb

This generates the language L(G) = {a^n b^n : n >= 0}. The Kleene
closure of L(G) is {(a^n b^n)^m : n,m >= 0}.

Applying the Lewis-Papadimitriou transformation you mentioned yields the
grammar G' = (S, {a,b}, P', S) where P' contains the single rule:

S -> \epsilon | aSb | SS

This generates a larger language. For instance, aababb is in L(G')
but not in the Kleene closure of L(G). In general, if S appears on the
right-hand side of a rule, then the Lewis-Papadimitriou transformation
looks dubious.

Thank you for your answer.

By the way, I think the Kleene closure of L(G) is
{a^{n_1}b^{n_1}...a^{n_k}b^{n_k} | k >= 0 and n_i >=0 for all i}.

.