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