DFA란 무엇인가?
DFA(Deterministic Finite Automata, 결정적 유한 오토마타)는 주어진 문자열을 수용하거나 거부하는 유한 상태 기계(Finite State Machine)입니다. 각 입력 심볼에 대해 현재 상태에서 다음 상태로의 전이가 하나로 결정되는 것이 DFA의 핵심 특징입니다.
이번 글에서는 입력 알파벳 집합 {a, b}로 구성된 문자열 중, 'a'로 시작하고 'a'로 끝나는 문자열을 수용하는 DFA를 설계하고 이를 C++ 코드로 구현해 보겠습니다.
수용 및 거부 조건
설계하려는 DFA가 판별하는 문자열의 유효 여부는 다음과 같습니다.
수용되는 문자열 예시
- ababba
- aabba
- aa
- a
위 문자열들은 모두 첫 번째 문자와 마지막 문자가 'a'이므로 DFA에 의해 수용됩니다.
거부되는 문자열 예시
- ab
- b
- aabab
'ab'와 'aabab'는 마지막 문자가 'b'이고, 'b'는 첫 문자 자체가 'a'가 아니므로 모두 거부됩니다.
C++ 구현 예제
다음 프로그램은 문자열이 'a'로 시작하고 'a'로 끝나는지 검사합니다. DFA의 동작 원리와 마찬가지로, 첫 번째 문자와 마지막 문자의 일치 여부만 확인하면 되고 그 사이의 문자들은 (a, b) 중 어떤 것이 와도 상관없습니다.
#include <iostream>
#include <string.h>
using namespace std;
int main() {
char str[] = "ababba";
int length = strlen(str);
if (str[0] == 'a' && str[length - 1] == 'a') {
printf("Accepted");
} else {
printf("Rejected");
}
return 0;
}
출력 결과
Accepted
동작 원리 설명
이 코드의 검사 로직은 DFA의 상태 전이 개념과 정확히 대응됩니다.
- 초기 상태: 문자열의 첫 문자를 확인하여 'a'인지 검사합니다. 'a'가 아니면 즉시 거부 상태로 전이됩니다.
- 중간 상태: 첫 문자가 'a'라면 두 번째 문자부터 마지막 앞 문자까지는 'a' 또는 'b' 어떤 값이 와도 상태를 유지할 수 있습니다.
- 최종 상태: 마지막 문자가 'a'이면 수용(Accepted) 상태에 도달하고, 그렇지 않으면 거부(Rejected) 상태가 됩니다.
예제 문자열 "ababba"는 첫 문자 'a', 마지막 문자 'a'를 만족하므로 "Accepted"가 출력됩니다. 이처럼 DFA는 복잡해 보이는 언어 조건도 단순한 상태 전이 규칙으로 표현할 수 있으며, 컴파일러의 어휘 분석기나 패턴 매칭 등 다양한 분야에서 활용됩니다.