Sind diese Sprachen REGULAR/CONTEXT FREE, aber nicht REG/Nothing?

Question

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

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

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

1) Keine Ahnung, für diese ein.

2) Ich denke, es ist kontext ist Ursache gibt es keine Beschränkung auf n, im Gegensatz zu 3) können wir nicht finit automatisieren bauen, aber wir können eine Grammatik bauen:

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

X ---> aabbb | aaXbbb 

3) Für mich ist es ein regelmäßiges ist Sprache wegen der Beschränkung auf den Wert von n, die es uns erlauben, es mit einem Automaten darzustellen.

Answer 1

(1) ist regelmäßig. Ein regulärer Ausdruck ist:

(aabbbbabaabbbbabaabbbbab)* 

(2) ist kontextfrei, aber nicht regelmäßig. Um zu sehen, es nicht regelmäßig ist, verwenden Sie das Pumpen von Lemma auf der Saite:

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

Argumentieren, daß das Pumpen nur die Anzahl der eine ist verändert. Um zu sehen, es kontextfrei ist, ist hier ein CFG:

S := a^14 b^21 | aaSbbb 

(3) Dies ist regelmäßig, weil es eine endliche Sprache ist, die aus den folgenden acht Worten:

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