티스토리 뷰
백엔드 개발하다 보면 정규식 많이 쓰잖아요. 이메일 검증이나 입력값 체크할 때 말이죠.
그런데 어느 날 "정규식이 유한상태기계다"라는 말을 듣고... 솔직히 뭔 소리인지 모르겠더라고요.
그래서 파헤쳐봤습니다.
유한상태기계가 뭔데?
일단 이름부터가 어려워 보이죠. 근데 개념은 생각보다 간단해요.
TV 리모컨 생각해보세요.
TV 꺼짐 --전원버튼--> TV 켜짐
TV 켜짐 --전원버튼--> TV 꺼짐
이게 유한상태기계예요. TV는 항상 "꺼짐" 아니면 "켜짐" 둘 중 하나 상태에 있고, 전원버튼 누르면 상태가 바뀌는 거죠.
신호등도 마찬가지:
빨간불 → 초록불 → 노란불 → 빨간불 (반복)
핵심은 이거예요:
- 지금 어떤 상태인지 기억하고 있음
- 뭔가 입력이 들어오면 (시간 지남, 버튼 누름 등)
- 정해진 규칙대로 다른 상태로 바뀜
그게 정규식이랑 무슨 상관?
처음엔 저도 이해 안 됐어요. 근데 생각해보니까...
정규식 abc를 예로 들어볼게요. 이게 "abc라는 문자가 순서대로 나오는지 확인하는 기계"라고 생각해보면:
시작 --'a'보면--> "a 찾음" --'b'보면--> "ab 찾음" --'c'보면--> "성공!"
"xabcy"라는 문자열이 들어온다면:
- 'x' 봄 → 아직 시작 상태
- 'a' 봄 → "a 찾음" 상태로 바뀜
- 'b' 봄 → "ab 찾음" 상태로 바뀜
- 'c' 봄 → "성공!" 상태
- 'y' 봄 → 이미 성공했으니 상관없음
이게 바로 유한상태기계죠!
CPU는 이걸 어떻게 처리할까?
고수준 언어에서는 간단해 보이지만, CPU 레벨에서 보면 정말 흥미로워요.
입력 "xabcy"를 처리하는 과정:
# 1단계: 'x' 처리
LOAD R1, 'x' # 메모리에서 'x' 로드
LOAD R2, 'a' # 현재 기대하는 문자는 'a'
CMP R1, R2 # 'x'와 'a' 비교
JNE STAY_START # 다르므로 START 상태 유지
MOV R3, 0 # state = START (0)
# 2단계: 'a' 처리
LOAD R1, 'a' # 다음 문자 'a' 로드
CMP R1, R2 # 'a'와 'a' 비교
JEQ FOUND_A # 같으므로 FOUND_A로 점프
MOV R3, 1 # state = FOUND_A (1)
MOV R2, 'b' # 이제 'b'를 기대
# 3단계: 'b' 처리
LOAD R1, 'b' # 다음 문자 'b' 로드
CMP R1, R2 # 'b'와 'b' 비교
JEQ FOUND_AB # 같으므로 FOUND_AB로 점프
MOV R3, 2 # state = FOUND_AB (2)
MOV R2, 'c' # 이제 'c'를 기대
# 4단계: 'c' 처리
LOAD R1, 'c' # 다음 문자 'c' 로드
CMP R1, R2 # 'c'와 'c' 비교
JEQ SUCCESS # 같으므로 SUCCESS로 점프
MOV R3, 3 # state = SUCCESS (3)
MOV R4, 1 # result = true
쉬프트 연산의 실체
여기서 "쉬프트"라고 말한 건 사실 문자 스트림을 순차적으로 읽는 과정이에요:
// Java 코드로 보면
String input = "xabcy";
int position = 0;
while (position < input.length()) {
char currentChar = input.charAt(position); // 현재 위치 문자 읽기
// 상태 전이 로직
switch (currentState) {
case START:
if (currentChar == 'a') currentState = FOUND_A;
break;
// ...
}
position++; // 다음 문자로 이동 (이게 "쉬프트")
}
참/거짓 저장하는 방식
결과를 저장하는 방식도 흥미로워요:
# 불린 값은 보통 1비트지만, CPU는 보통 8비트 단위로 처리
MOV R4, 0 # false = 0
MOV R4, 1 # true = 1
# 조건 플래그 레지스터 활용
CMP R1, R2 # 비교 후 플래그 설정
JZ SUCCESS # Zero Flag가 설정되면 (같으면) 성공
# 실제로는 이런 식으로 최적화
TEST R4, R4 # R4가 0인지 체크
JNZ FOUND # 0이 아니면 (true면) 찾음
메모리 접근 패턴의 차이
생각해보면 스택과 무엇이 다를까요? .. 본질은 무언가 상태를 저장하고 비교하는건 똑같잖아요..?
하지만, 공부해보니.. 생각보다 다르더라구요..
스택 방식(이해를 위한 예시.. 쓰이지는 않음):
# 매번 다른 스택 위치에 접근
PUSH 'a' # 스택[0] = 'a'
PUSH 'b' # 스택[1] = 'b'
PUSH 'c' # 스택[2] = 'c'
# 나중에 POP으로 꺼내서 비교
POP R1 # 'c' 꺼냄
POP R2 # 'b' 꺼냄
POP R3 # 'a' 꺼냄
상태기계 방식:
# 항상 같은 레지스터만 사용
MOV R3, 0 # state = START
MOV R3, 1 # state = FOUND_A
MOV R3, 2 # state = FOUND_AB
MOV R3, 3 # state = SUCCESS
실제 필요한 최소 저장공간
하드웨어 레벨에서 정말 필요한 공간을 계산해보면:
// "abc" 패턴 매칭에 필요한 최소 비트
byte currentChar; // 8비트 (현재 문자)
byte expectedChar; // 8비트 (기대하는 문자)
byte state; // 2비트 (4가지 상태: START, FOUND_A, FOUND_AB, SUCCESS)
boolean found; // 1비트 (찾았는지 여부)
// 총 19비트 (약 3바이트)
이론적으로는 더 줄일 수도 있어요
// 극한 최적화
byte currentChar; // 8비트
byte state; // 2비트 (상태 정보에 기대 문자도 포함)
boolean found; // 1비트
// 총 11비트
스택 방식이 입력 길이 × 8비트 (예: "xabcy" = 40비트) 쓰는 거랑 비교하면 엄청난 차이죠.. 근데 느릴듯?..
왜 상태기계가 캐시에 유리한가?
# 상태기계: 같은 레지스터 반복 사용
MOV R3, 0 # 캐시에 R3 로드
MOV R3, 1 # R3는 이미 캐시에 있음
MOV R3, 2 # R3는 이미 캐시에 있음
# 스택: 매번 다른 메모리 위치 접근
MOV [SP+0], 'a' # 스택 위치 0에 저장
MOV [SP+1], 'b' # 스택 위치 1에 저장 (캐시 미스 가능)
MOV [SP+2], 'c' # 스택 위치 2에 저장 (캐시 미스 가능)
CPU 입장에서는 이런 미세한 차이들이 모여서 큰 성능 차이를 만들어내는 거예요.
결론
정규식이 유한상태기계라는 건
- 메모리 효율적이고
- 빠르고
- 캐시 친화적이라는 뜻
하지만 표현력에는 한계가 있어서, 실제 Java 정규식 엔진은 간단한 패턴은 상태기계로, 너무 복잡한걸 처리하는건 지양하는게 좋습니다.
이제 정규식 쓸 때마다 "아, 지금 내부에서 상태기계가 돌고 있구나" 생각하게 되네요.
그냥 쓰기만 했는데 이런 원리가 있었다니... 컴퓨터과학이 참 재밌어요.