크레이 네 스타에 대한 혼란

Question

나는 두 개의 노동 조합 식의 폐쇄에 대한 핵심 속성 중 하나를 이해하기 위해 애 쓰고 있습니다. 기본적으로 클라인 스타가 어떻게 작동하는지 정확히 알 필요가 있습니다.

IE 만약 정규 표현식 R = (0 + 1) *합니까 표현은 000111/01/00001111 같은으로 평가해야한다, 또는 우리는 0011111/000001로, 0의 & 1의의 불평등 한 금액을 가질 수있다/111111/0000?

Answer 1

0과 1의 양은 서로 다를 수 있습니다. 어떤 순서로도 0과 1을 가질 수 있습니다! a*은 "a이 0 이상인 것을 의미합니다. 각 a은 독립적으로 평가됩니다"; 따라서 (0+1)*과 일치하는 문자열에서 각 문자는 문자열의 다른 문자가 일치하는 것과 상관없이 (0+1)과 일치 할 수 있습니다.

패턴을 고려하십시오. (0+1)(0+1); 문자열 00, 01, 10 및 11과 일치합니다. 보시다시피, 0과 1은 같은 양으로 발생할 필요가 없으며 특정 순서로 발생할 필요가 없습니다. Kleene 스타는 이것을 임의의 길이의 문자열로 확장합니다. 결국 (0+1)*은 <empty>+(0+1)+(0+1)(0+1)+(0+1)(0+1)(0+1)+ ...을 의미합니다.