Regular Expressions: Creating Binary String Patterns

정규 표현식(Regular Expression) - 시작이 10인 이진 문자열

1. 문제 정의

주어진 언어 ( L )은 "10"으로 시작하는 모든 이진 문자열입니다.
즉, 첫 두 자리가 반드시 "10"이어야 하며, 이후에는 0과 1이 자유롭게 조합될 수 있습니다.
이를 정규 표현식으로 표현해 보겠습니다.

---

2. 정규 표현식의 구성

(1) "10"으로 시작하는 문자열

첫 두 자리가 "10"으로 고정되어 있어야 하므로, 표현식의 시작은 다음과 같습니다.

10

(2) "10" 이후의 문자열

"10" 뒤에는 0과 1이 자유롭게 조합될 수 있으므로, 클레이니 스타(Kleene Star, *)를 사용합니다.

(0|1)*

이 표현식은 0과 1이 반복될 수 있음을 의미합니다.

---

3. 최종 정규 표현식

위 두 부분을 결합하면 최종 정규 표현식이 완성됩니다.

10(0|1)*

---

4. 추가 예제

(1) "100"으로 끝나는 이진 문자열

문자열이 "100"으로 끝나야 한다면, 앞부분은 자유롭게 조합 가능하며, 마지막 세 자리는 "100"이어야 합니다.

(0|1)*100

(2) "10"으로 시작하고 "100"으로 끝나는 이진 문자열

10(0|1)*100

---

정규 표현식 - 끝이 10 또는 01인 이진 문자열

1. 문제 정의

주어진 언어 ( L )은 "10" 또는 "01"로 끝나는 모든 이진 문자열입니다.
즉, 마지막 두 자리가 반드시 "10" 또는 "01"이어야 합니다.

---

2. 정규 표현식의 구성

(1) "10" 또는 "01"로 끝나는 문자열

(10|01)

(2) "10" 또는 "01" 앞의 문자열

마지막 두 자리를 제외한 나머지는 자유롭게 조합될 수 있습니다.

(0|1)*

---

3. 최종 정규 표현식

(0|1)*(10|01)

---

4. 추가 예제

(1) "00" 또는 "11"로 끝나는 이진 문자열

(0|1)*(00|11)

(2) "10"으로 시작하고 "01"로 끝나는 이진 문자열

10(0|1)*01

---

정규 표현식 - 네 번째 기호가 1인 이진 문자열

1. 문제 정의

주어진 언어 ( L )은 네 번째 자리가 반드시 1인 이진 문자열입니다.
즉, 문자열의 네 번째 기호는 항상 1이어야 합니다.

---

2. 정규 표현식의 구성

(1) 네 번째 기호가 반드시 1

처음 세 자리에는 0 또는 1이 자유롭게 올 수 있으며, 네 번째 자리는 1로 고정됩니다.

(0|1){3}1

(2) 네 번째 기호 이후의 문자열

네 번째 기호 이후에는 자유로운 조합이 가능합니다.

(0|1)*

---

3. 최종 정규 표현식

(0|1){3}1(0|1)*

---

4. 추가 예제

(1) 다섯 번째 기호가 반드시 0인 이진 문자열

(0|1){4}0(0|1)*

(2) 우측에서 네 번째 기호가 반드시 1인 이진 문자열

(0|1)*1(0|1){3}

---

정규 표현식 - 특정 길이를 갖는 이진 문자열

1. 문제 정의

이진 문자열의 길이를 기준으로 다음 세 가지 경우를 고려합니다.

1. 길이가 정확히 3인 문자열
2. 길이가 최대 3(0, 1, 2, 3 중 하나)인 문자열
3. 길이가 최소 3(3 이상)인 문자열

---

2. 정규 표현식의 구성

(1) 길이가 정확히 3인 문자열

각 자리에서 0 또는 1이 올 수 있도록 (0|1)을 3번 반복합니다.

(0|1){3}

✅ 허용 예: 000, 011, 101
❌ 허용되지 않음: 00, 1111, 1

---

(2) 길이가 최대 3인 문자열

길이가 0, 1, 2, 3인 문자열을 포함해야 하므로, {0,3}을 사용합니다.

(0|1){0,3}

입실론을 통해 다음과 같이 표현할 수 있습니다

(0|1|ε){3}

또는 개별적으로 나열할 수도 있습니다.

ε | (0|1) | (0|1){2} | (0|1){3}

✅ 허용 예: ε(빈 문자열), 0, 1, 11, 101, 110
❌ 허용되지 않음: 1000, 1111

---

(3) 길이가 최소 3인 문자열

최소 세 개의 0 또는 1이 포함되어야 하며, 이후에는 자유로운 조합이 가능합니다.

(0|1){3}(0|1)*

✅ 허용 예: 000, 111, 101, 1100, 00101
❌ 허용되지 않음: 0, 11, 1

---

정규 표현식(Regular Expression) - 특정 길이를 갖는 이진 문자열

1. 문제 정의

주어진 언어 ( L )은 이진 문자열의 길이에 따라 다음 세 가지 경우로 분류됩니다.

1. 길이가 짝수인 문자열
2. 길이가 홀수인 문자열
3. 길이가 3의 배수인 문자열

이를 정규 표현식으로 표현해 보겠습니다.

---

2. 정규 표현식의 구성

(1) 길이가 짝수(Even)인 문자열

문자열의 길이가 항상 짝수(0, 2, 4, 6...)여야 합니다.
따라서, 짝수 개의 0과 1이 반복되는 구조를 만들면 됩니다.

((0|1)(0|1))*
= ((0|1){2})*

✅ 허용 예: ε, 01, 10, 0011, 1100, 101010
❌ 허용되지 않음: 0, 1, 111, 10011

---

(2) 길이가 홀수(Odd)인 문자열

문자열의 길이가 항상 홀수(1, 3, 5, 7...)여야 합니다.
즉, 짝수 개의 비트가 반복된 후 단일 비트가 추가되어야 합니다.

(0|1)((0|1)(0|1))*
= (0|1)((0|1){2})*

✅ 허용 예: 0, 1, 011, 101, 11011, 100111
❌ 허용되지 않음: ε, 00, 1010, 110000

---

(3) 길이가 3의 배수(Multiple of 3)인 문자열

문자열의 길이가 3, 6, 9, ...처럼 3의 배수여야 합니다.
따라서, 각 세 개의 비트를 그룹으로 반복하면 됩니다.

((0|1)(0|1)(0|1))*
= ((0|1){3})*

✅ 허용 예: ε, 000, 101, 110, 001001, 111000, 100110
❌ 허용되지 않음: 0, 11, 1010, 1100000

---

정규 표현식 - 0의 개수에 따른 이진 문자열

1. 문제 정의

주어진 언어 ( L )은 이진 문자열에서 0의 개수가 특정 조건을 만족하는 경우로 분류됩니다.

1. 0이 정확히 2개인 문자열
2. 0이 최대 2개인 문자열
3. 0이 최소 2개인 문자열
4. 0이 짝수 개(2의 배수)인 문자열
5. 0이 홀수 개인 문자열
6. 0이 3의 배수(3n)인 문자열

이를 정규 표현식으로 표현해 보겠습니다.

---

2. 정규 표현식의 구성

(1) 0이 정확히 2개인 문자열

0이 정확히 두 개 포함된 문자열을 표현해야 합니다.
각 0 사이에는 1이 자유롭게 올 수 있습니다.

1*01*01*

✅ 허용 예: 001, 1001, 110011, 10101
❌ 허용되지 않음: 000, 11, 101, 0001

---

(2) 0이 최대 2개인 문자열

0이 0개, 1개, 2개까지 포함될 수 있는 문자열입니다.

1* | 1*01* | 1*01*01*

입실론을 통해 다음과 같이 표현할 수 있습니다

1*(0|ε)1*(0|ε)1*
= 1*(0|ε)1*

✅ 허용 예: 111, 101, 1001
❌ 허용되지 않음: 000, 1100110

---

(3) 0이 최소 2개인 문자열

0이 2개 이상 포함된 문자열입니다.
즉, 최소한 2개의 0이 포함된 후 자유롭게 조합될 수 있습니다.

(0|1)*0(0|1)*0(0|1)*

✅ 허용 예: 001, 1001, 110001, 1010010
❌ 허용되지 않음: ε, 1, 101

---

(4) 0이 짝수 개(2의 배수)인 문자열

0이 짝수 개(2, 4, 6...) 포함된 문자열입니다.
즉, 0을 두 개씩 그룹으로 묶어야 합니다.

1*(1*01*01*)*

✅ 허용 예: ε, 0011, 100011, 11000011
❌ 허용되지 않음: 0, 101, 110010

---

(5) 0이 홀수 개인 문자열

0이 1, 3, 5, 7... 개 포함된 문자열입니다.
짝수 개의 0을 포함하는 패턴에 마지막에 0을 하나 추가하면 됩니다.

(1*01*0)*1*0

✅ 허용 예: 0, 100, 11001, 1010001
❌ 허용되지 않음: ε, 1010, 100011

---

(6) 0이 3의 배수 개(3n 개)인 문자열

0이 3, 6, 9... 개 포함된 문자열입니다.
각 세 개의 0이 자유롭게 등장할 수 있도록 합니다.

1*(1*01*01*0)*

✅ 허용 예: 000, 1000100, 110100010
❌ 허용되지 않음: ε, 0, 11000, 101000