이 언어는 REGULAR/CONTEXT FREE이지만 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)이 하나 없음 단서.

2) 3와 달리, N에 제한이없는 원인이 contextFree을 생각) 우리가 finit의 자동화를 구축 할 수 없지만 우리는 문법 구축 할 수 있습니다 : 그것은 일반의 나에게

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

X ---> aabbb | aaXbbb 

3) 왜냐하면 우리가 자동화로 그것을 표현할 수있게 해주는 n 값의 한계 때문이다.

Answer 1

(1)은 규칙적입니다. 정규 표현식은 다음과 같습니다.

(aabbbbabaabbbbabaabbbbab)* 

(2) 컨텍스트는 없지만 규칙적입니다. 그것은 일반 아니다 보려면, 문자열에 펌핑 보조 정리를 사용

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

은 펌핑이 단지의 수를 변경 주장한다. 이 문맥 무료로 보려면 여기 CFG의 :

S := a^14 b^21 | aaSbbb 

는 다음과 같은 여덟 개 단어로 구성된 유한 한 언어이기 때문에 (3)이 정규이다 :

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 

가