0
다음 문제를 해결하기 위해 애 쓰고 있습니다. 나는 펌핑 보조 정리를 사용해야합니다.문맥 자유 언어 (펌닝 보조 언어^^ b^m c^min (n, m))
{a^n b^m c^min (n, m) | m, n> = 0}은 컨텍스트 프리가 아닙니다.
A
답변
1
언어로 a^p b^p c^p 문자열을 고려하십시오. 문맥없는 언어에 대한 펌핑 - 보조 정리에 의해,이 문자열은 다음과 같이 uvxyz로 쓰여질 수 있습니다.
- | vxy | <p
- | vy |
- 유 (V^N) × (Y^n)를 z는 모든 자연수에 대한 언어 N에도> 0
우리의 문자열에 vxy의 위치에 대한 고려 오가지 경우가 있습니다
vxy는 전적으로 a의 첫 번째 섹션에 있습니다. n = 0을 선택하고 펌프를 작동 시키면 a의 값을 잃지 만 c의 수는 언어에 남아 있기 위해 줄여야합니다. 이 vxy 배치는 작동하지 않습니다.
vxy는 a와 b를 포함합니다. n = 0을 선택하고 펌핑 다운하면 a와 b가 손실됩니다. c의 수가 비례 적으로 감소하지 않기 때문에, vxy에 대한이 선택은 작동하지 않습니다.
vxy는 완전히 b 섹션에만 있습니다. Case 1의 동일한 주장이 여기서도 적용됩니다.
vxy는 a의 광고를 포함합니다. n> 0을 선택하고 펌핑하면 b와 c가 추가됩니다. 이제 c의 수는 a의 수보다 엄밀히 많을 것입니다. 이는이 선택이 작동하지 않는다는 것을 의미합니다.
vxy는 전체적으로 c 섹션에만 있습니다. 양방향으로 펌핑하면 c의 수는 a의 수와 b의 수와 다르므로 선택도 실패합니다.
문자열에 vxy을 넣을 수있는 위치는 다섯 곳이었으며 모두 실패했습니다. 즉, 펌핑 보조 정리의 요구 사항에 따라 문자열을 작성할 수 없으므로 언어가 문맥에 자유로울 수 없습니다.