폐쇄 특성

Question

I 다음과 같은 문제가있다 :

언어 L1 = {A^N * B^N : N> = 0} 및 L2 = {B^N 개의 * A를^N을 : n> = 0}은 컨텍스트가없는 언어이므로 L1L2에서 닫히므로 L = {a^n * b^2n A^n : n> = 0}은 클로저 속성.

사실인지 아닌지를 증명해야합니다. 그래서 L 언어를 확인한 결과 문맥 상 자유가 없다고 생각하지 않고 L2가 단지 반전 된 것을 보았습니다.

L1, L2가 결정적인지 확인해야합니까?

Answer 1

L1 = {A, B ^N N : N> = 0} 및 L2 = {N b를 N : N> = 0} 모두 문맥 자유 롭다.

컨텍스트가없는 언어는 연결 상태로 닫히기 때문에 L3 = L1L2도 컨텍스트가 없습니다.

그러나, L3 = L4는 동일한 언어 아니다 {A ^N B ^2N N : N> = 0}. 문자열 abbbaa은 L3에 있지만 L4에는 없습니다.

L4 컨텍스트 프리입니까? 그렇다면 pumping lemma for context-free languages을 준수해야합니다.

p를 펌핑 길이를 L4로합시다. s = a ^p b ^2pp을 선택하십시오. 그러면 s가 L4에 있고 | s | > p. 따라서 L4가 컨텍스트 프리 인 경우 다음과 같이 쓸 수 있습니다.을 uvxyz로, | vxy | < = p, | vy | > = 1, 및 UV ^N XY ^N Z는 위해 L4 임의 N>은 = 0

L4의 모든 비어 있지 않은 문자열의 다음 속성을 관찰 : A들 카운트 B 년대 카운트 같다. 부분 문자열 'ab'가 정확히 하나만 존재하고 부분 문자열 'ba'가 정확히 하나만 존재합니다 ( ). a의 최초의 캐릭터 라인의 길이는, a의 마지막 캐릭터 라인의 길이와 동일합니다.

우리는 이러한 관찰을 사용하여 L4의 펌핑 인수에서 v와 y의 가능한 선택을 제한 할 수 있습니다. v와 y는 부분 문자열 'ab'를 포함 할 수 없습니다. 왜냐하면 v와 y는 임의의 횟수만큼 펌핑되므로 출력 문자열에는 'ab'가 여러 번 포함되므로 L4의 요소가 될 수 없기 때문입니다. 동일한 인수가 하위 문자열 'ba'에도 적용됩니다.

그래서 v는 비어 있거나 모두 또는 모두이어야합니다. y도 마찬가지다.

또한 v가 모두 a이면 y는 같은 수의 b로 구성되어야합니다. 그렇지 않은 경우 펌핑 된 문자열에는 v와 y가 동일한 n이 에 의해 펌핑되므로 a와 b의 수가 동일하지 않습니다. 마찬가지로 v가 모두 b이면 y는 a와 같아야합니다.

그러나 v가 모두 a이고 y가 모두 b 인 경우 a의 마지막 문자열은 v와 y를 펌핑하여 영향을받지 않으므로 a의 선행 문자열은 더 이상 a의 후행 문자열과 일치하지 않습니다. 마찬가지로, v가 모두 b이고 y가 모두 a 인 경우, a의 앞과 뒤의 문자열은 다시 v와 y가 펌핑되는 것과 다른 길이를 갖습니다.

v와 y는 둘 다 비어있을 수 없습니다. 이는 | vy | > = 1 일 때 CFL 펌핑 보조 정리. 그러나 우리는 그것을 | v | = | y | 일 때, v와 y가 비어 있지 않은 것은 다음에옵니다.

그러나 V가 비어있을 수없는 경우, 모든 ㄱ의 수 없으며 하위 문자열 'AB'또는 '바'를 포함 할 수 없습니다, 모두의 수 없습니다, 다음의 펌핑 버전을 하는 uvxyz의 어떤 가능한 선택이 없다 아직 L4에 있습니다. 따라서 L4는 컨텍스트 프리가 아닙니다.

Answer 2

L1 및 L2의 정의에서 해당 정의 내에서 n의 범위가 지정됩니다. 즉 두 개의 다른 변수입니다. 당신이 그들을 결합하면 하나의 이름을 변경하고 대신 얻어야한다 :

L = {a^n * b^n b^m * a^m : n,m>=0} 

이 당신의 L에서 매우 다른 언어이지만, 분명히 상황 무료입니다.