다음 언어와 일치하는 정규 표현식을 구성하십시오.

Question

강의가 끝날 때 내 교수가 생각한 운동을하고 있습니다. 문제는 특정 언어 정의가 지정된 DFA를 구성하는 것입니다. DFA를 작성하기 전에 먼저 언어 정의를 정규 표현식으로 변환해야합니다.

제공된 알파벳 이진 {0, 1}

언어 정의는 매우 약식 :

길이 3의 모든 서브 스트링으로서 갖는 이진 스트링의 세트를 정의 언어 적어도 제로

하나 그래서이 정의와 일치 문자열의 예 등 000, 001, 1010 및 될 것입니다.

이 언어 정의와 일치하는 정규 표현식에 문제가 있습니다. 나는 http://regexr.com/에서 놀아 보았습니다. 그러나 그저 '..0'은 세 문자마다 끝에 0이 붙는 것을 발견했습니다. 언어가 정의 된 방식으로 모든 하위 문자열을 일치시키는 방법이나 가능한지 확실하지 않습니다.

이 문제에 대한 정규 표현식을 만드는 방법이 있습니까?

Answer 1

측방 사고가 필요합니다. 비공식 언어 정의에 대한 정규 표현식을 구현하지 말고 그 정의가 의미하는 특성에 대해 구현하십시오.

스포일러 (용액 대 위에 마우스 오버)

힌트 1

임의의 3 길이의 문자열이 다음에, 0 -digit 있어야한다면 행의 3 자리 숫자가 1-digit 인 것은 불가능합니다.

힌트 2

은

이 0 매 사이 -digit 1 -digits 많아야 2 존재한다는 것을 의미한다.

힌트 3 :

이는 0-2 1 -digits 후하는 0 -digit로 구성된 그룹의 가능성이 무한한 양이 오는 언어합니다 0-2 1- 디지트.

솔루션 :

^1{0,2}(01{0,2})*$, 또는 동등보다 수학적으로 , 이것은 대단한 ^(11?)?(0(11?)?)*$