Search code examples
context-free-grammarregular-languagecontext-free-language

Is this languages REGULAR / CONTEXT FREE but not REG / Nothing?

(1) {((a^2)(b^4)ab)^(3k) : k>=0}

(2) {a^(2n)b^(3n) : n >= 7}

(3) {a^(2n)b^(3n) : n <= 7}

In order to see more clearly the Languages

  1. No clue for this one.

  2. I think it's contextFree cause there is no limitation on n, unlike 3) we can't build a finite automate but we can build a Grammar:

    S ---> (a^14)X(b^21)

    X ---> aabbb | aaXbbb

  3. For me it's a regular language because of the limitation on the value of n which allow us to represent it with an automate.

Solution

  • (1) is regular. A regular expression is:

    (aabbbbabaabbbbabaabbbbab)*

    (2) is context free but not regular. To see it's not regular, use the pumping Lemma on the string:

    a^(14p) b^(21p)

    Argue that pumping changes the number of a's only. To see it is context free, here's a CFG:

    S := a^14 b^21 | aaSbbb

    (3) This is regular because it is a finite language consisting of the following eight words:

    e
a^2 b^3
a^4 b^6
a^6 b^9
a^8 b^12
a^10 b^15
a^12 b^18
a^14 b^21