Kleene Star Closure of Regular Grammars

Algorithm

Given regular grammar G, we would like to construct a regular grammar G' such that L(G') = (L(G))*:

  1. construct the kleene plus of the regular grammar (see the relevant section);
  2. add to the language (see the relevant section)

Example

Give a regular grammar recognising the Kleene star closure of the language recognised by the following grammar:

S aA | bB
A aA | a
B c | bS

where S is the start symbol.

  1. Construct the Kleene plus closure of the language:

    S aA | bB
    A a | aA | aS
    B c | cS | bS

    where S is the start symbol.

  2. Add to the language:

    S1 | aA | bB
    S aA | bB
    A a | aA | aS
    B c | cS | bS

    where S1 is the start symbol.

Exercises

Construct regular grammars which recognise the Kleene star closure of the languages described using the following regular grammars:

  1. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC,
    A aA | bB | ,
    B bB | b | ,
    C cB | cC | },
    S >
  2. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC | ,
    A aA | aS,
    B b,
    C cB | cS },
    S >
  3. G = < { a, b, c },
    { S, A, B, C },
    { S aA | bC | ,
    A aA | aS,
    B b,
    C cB | cS },
    S >
  4. G = < { a, b },
    { S, A },
    {S aA | bS,
    A },
    S >
  5. G = < { a },
    { S },
    { S},
    S >