RE : 정확하게 두 개의 0을 포함하는 {0, 1}을 초과하는 이상한 길이의 문자열

Question

방금 ​​공식 lang 및 automata 이론에 대해 배우기 시작했습니다. 최근에 정규 표현식에 대해 배웠으므로 복잡한 기호를 모르므로 기본 기호.

질문은 다음 언어에 대한 정규 표현식을 0을 정확히 포함하는 모든 홀수 길이 문자열의 집합 인 {0, 1}을 작성합니다.

나는 첫 번째 부분 (홀수 부분)을 완료있어

, 그것은해야한다 :

(0+1)[(0+1)(0+1)]* (| (또는) 저는 믿습니다, 우리가 +로 배운 +은 동일) 그러나 정확하게 두 개의 0을 가지고 있다고 생각하면 엉망이됩니다. # 0의 숫자가 2으로 제한되어 있기 때문에 *을 1과 함께 사용할 수 있음을 알 수 있습니다. 그러나 내가 (11)*을 수행하면 안에 0의 순열을 가져올 수 없습니다. (예 : 을 (11)*으로 가져올 수 없음).

내가 알고있는 무엇 :

1. 만 1의가에 홀수 길이를 추가하는 두 0의 홀수 길이를 만들기 위해
2. 방법을 사용되는 정규 표현식에서 *
3. 입니다 사용할 수 있습니다 짝수 길이는 짝수 길이가 * 일 수 있기 때문에 *을 사용해서는 안되며, 따라서 홀수 길이는 두 개의 홀수 = 짝수이므로 *을 사용해서는 안됩니다.
가능 힌트 나 답을

, 사용하십시오 0, 1, +/|, *, (, ) 만. 내가 이해할 수없는 다른 표현들.

Answer 1

정확히 두 0가 포함 된 모든 홀수 길이 문자열의 집합 정규 언어{0, 1} 이상.

이 언어는 무엇을 의미합니까?

주 언어 스트링 두 0 구성 및 임의의 수의 수 1 문자열의 전체 길이가 홀수되도록. 다른 제한 사항은 없습니다. 01와는 임의의 순서 및 임의의 패턴으로 나타난다.

우리가 알고있는 바로는 even + odd = odd입니다. 문자열 그래서하는 문자열 0의 수가 2이기 때문에 적어도 세 가지 길이와 1의 홀수로 구성되어있다. A 0 B A는, B, C,있는 문자열은 1 및 1의 총 개수로 구성 0 C :

그래서 정규 표현식 같은 것을해야한다 A, B, C는 홀수이므로 표현식에 모두 ^ (nul)이 될 수 없습니다.

하기 때문에 홀수 A, B, C = 의 1의 총 개수는 다음과 같을 수있다 : 그래서, 어느 1 two even and one odd 또는 (2)를 all three are odd.

참고 : 홀수 길이 문자열은 null 일 수 없습니다.

정규 표현식은 :

1(11)*01(11)*01(11)* + 1(11)*0(11)*0(11)* + (11)*01(11)*0(11)* + (11)*0(11)*01(11)* 
// all odd    A odd, B C even  B odd, A C even  A B even, C odd