언어가 규칙 적인지 시연하십시오

Question

다음 언어의 규칙 성을 입증해야합니다 : {xy ∈ {a, b} * | | X | _a = 2 | Y | _b} 이는 xy 형식의 단어를 말하며, 여기서 서브 단어 x의 어커런스 수는 서브 단어 y에서 b의 어커런스 수의 두 배입니다. 나는 그것이 규칙적이라고 생각하지만 그것을 증명하는 방법을 모른다. 사전

Answer 1

에서

덕분 언어 :

{ xy in {a,b}* such that |x|a = 2|y|b } 

언어 (aa)* = {e, aa, aaaa, ...}에 문자열을 고려하십시오. Myhill-Nerode 정리의 구별 할 수없는 관계로이 문자열 각각을 구별 할 수 있습니다. 이는 언어에 대한 모든 DFA가 무한히 많은 주, 모순을 가져야 함을 의미합니다.

e을 언어가 아닌 문자열로 가져 오는 가장 짧은 문자열은 ab입니다. 언어가 아닌 문자열에 aa이 걸리는 가장 짧은 문자열은 abb입니다. 언어가 아닌 문자열에 aaaa을 사용하는 가장 짧은 문자열은 abbb입니다. 일반적으로 a^(2n)을 언어가 아닌 문자열로 취하는 가장 짧은 문자열은 ab^(n+1)입니다. 이러한 문자열의 형식은 a^(2n+1) b^(n+1)이며 하나의 언어로는 a이 누락되어 있습니다. (aa)* 양식의 모든 문자열은이 언어에 대해 최소 DFA을 다른 모든 언어와 다른 상태로 유도해야합니다.

또 다른 방법은 폐쇄 속성을 사용하는 것입니다. 일반 언어는 교차로에서 닫힙니다. 이 언어와 일반 언어 a(aa)*b*의 교차로를 선택하십시오. 이제 |x|a = 2|y|b 조건은 |w|a > 2|w|b 인 경우에만 명확하게 충족 될 수 있습니다. 우리가 a의

|w|a > 2|w|b 경우의 홀수 번호를 가지고 있기 때문에 |w|a = 2|w|b 불가능한 경우

• , 2|w|b 동일한 길이를 가지고 x을 선택합니다. y에는 약간의 추가 a이 있지만 괜찮습니다.
• |w|a < 2|w|b 인 경우 분할의 왼쪽에 b이 있어야하지만 a의 오른쪽으로 갈 때마다 왼쪽에 홀수 인 a이 있으므로 불가능합니다.

(b들과 같은보다 많은 a 배 이상의 S와 S b 하였다 a (S)의 홀수)이 조건 언어는 일반 언어 아니다. 이를 확인하기 위해 문자열 a^(2p+1) b^(p+1)과 정규 언어에 대한 펌핑 보조 정리를 사용하여 펌프가 b의 수를 변경하지 않고 a의 수를 줄일 수 있다고 주장 할 수 있습니다.