0
시험이 다가오고 있으며 교수님이이 정보를 포함 시키길 원합니다. 보조 정리가 어떻게 작동하는지 이해하지만 "펌핑"이 내부 또는 외부에서 얼마나 자주 발생 하는지를 개념화 할 수는 없습니다.reg 언어에 대한 펌핑 보조 정리의 어느 부분이 내가 펌핑하는지 또는 펌핑하는지, 그리고 몇 번 펌핑했는지 여부를 나타냅니다.
A
답변
0
정규 언어에 대한 펌핑 보조 정리는 형식 언어의 규칙성에 대한 충분 조건은 아니지만 필수 조건입니다. L이 정규 언어 인 경우 길이가 적어도 p 이상의 문자열 s = xyz가되도록 자연수 p가 있습니다.
- y는 길이가 적어도 하나입니다.
- xy는 p보다 크지 않은 길이를 가지고;
- x (y^n) p는 임의의 자연수 n에 대해서도 L에있다.
논리적으로, 조건은 다음과 같습니다 7 호선에
1. if (L is regular) then
2. there exists a natural number p such that
3. if s is in L and |s| >= p then
4. s = xyz
5. and |y| > 0
6. and |xy| <= p
7. and x(y^n)z is in L
, 우리는 s는 L.에 있어야 문자열의 버전을 참고 "펌프"라고하는 것이 N = 1, 우리의 자체 복구 ; 우리는 이미 3 번 줄에있는 가상의 것으로 L에 있다고 가정했습니다. "펌핑"또는 "펌핑"여부에 따라, 그리고 얼마만큼, n의 선택에 달려 있습니다. 일반 언어에 대한
펌핑 보조 정리는이 논리에 의해 작동 : 언어 일반입니다
- 경우에 대한 최소한의 DFA있다.
- 언어에 대한 최소 DFA가 p 상태 인 경우 길이가 p 이상인 언어의 문자열은 DFA가 일부 상태를 두 번 이상 방문하지 못하게해야합니다 (비둘기 원칙).
- DFA가 여러 번 상태를 방문한 경우 DFA에주기가 있고이 문자열로 인해 DFA가이주기를 통과하게됩니다. 주기 시간의 몇 가지 숫자를 DFA의 원인이 캐릭터 라인이, L 인 경우
- , 다음도
L.에 있어야주기 주위에 많은 시간 이하의 시간 여행을 다른 문자열이 있습니다 입력 문자열 X = 부품 일부 사이클
- P :이 논리 주어 하나의 사이클 실행 E
- Z = 약간의 사이클은, 예를 들면
0,1 0 /---\
--->(q0)--->(q1)--->(q2)<--/ 0,1
^ |
\------/
1
를 문자열 0100은 L. P는 = 3이고 | 0100 | = 4이므로 펌핑 보조 정리가 유지되어야합니다. x, y 및 z에 대한 우리의 유일한 선택은 x = 0, y = 10 및 z = 0입니다. 펌핑 보조 정리에서는 y를 없애거나 여러 배수를 더하고 L에서 다른 문자열을 얻을 수 있다고 주장합니다. y는 q1에서 q0까지의 루프이기 때문에 이것이 작동하는 것을 볼 수 있습니다. 우리는 그것을 건너 뛸 수 있거나 (n = 0) 반복 할 수 있습니다 (n> 1).