문자 'a'와 'b'로 구성된 문자열이 주어졌을 때, 이 문자열이 'a'로 시작하면서 'a'로 끝나는지 여부를 DFA(Deterministic Finite Automata)를 통해 판별하는 것이 이번 글의 목표입니다.
DFA(결정적 유한 오토마타)란 무엇인가?
이론 컴퓨터 과학의 한 분야인 계산 이론에서 결정적 유한 오토마타(DFA)는 기호(symbol)로 이루어진 문자열을 받아들이거나 거부하는 유한 상태 기계(finite state machine)입니다. 여기서 '결정적(deterministic)'이라는 말은 수행되는 계산 경로가 항상 유일하다는 의미입니다.
입력 알파벳 (a, b)에 대해 'a'로 시작하고 'a'로 끝나는 문자열을 DFA로 검사해야 하는데, DFA에는 메모리라는 개념이 없어 현재 문자만 저장할 수 있기 때문에 입력된 전체 문자열을 보관할 수 없습니다. 만약 메모리가 있다면 단순히 문자열의 첫 글자와 마지막 글자만 확인하면 되겠지만, DFA는 상태 전환만으로 이 문제를 해결해야 합니다.
예시
입력: a b b a 출력: yes 설명: 입력 문자열이 'a'로 시작하고 'a'로 끝납니다. 입력: a a a b a b 출력: no
위 문제를 해결하기 위한 접근 방식은 다음과 같습니다.
먼저 해당 문제에 맞는 DFA 상태 다이어그램을 설계합니다. 첫 번째 문자가 'a'면 시작 상태에서 유효 상태로 전이하고, 그 이후 문자열을 읽으면서 마지막으로 읽은 문자가 'a'인 경우에만 최종(허용) 상태에 머무르도록 상태 전이 규칙을 구성합니다. 그런 다음 설계한 DFA의 논리를 코드로 옮겨 문제를 해결합니다.
알고리즘
시작
1단계 -> main() 함수에서
난수 생성을 위해 srand(time(0)) 함수 호출
변수 선언: int max = 1 + rand() % 15
변수 선언 및 초기화: int i = 0
While(i < max)
char data = 'a' + rand() % 2 로 문자 생성
data 출력
i 증가
IF data == 'a'
IF(i == max)
"YES" 출력
종료
Loop While (i < max)
data = 'a' + rand() % 2
data 출력
i 증가
If (data == 'a' AND i == max)
"YES" 출력
종료
Else IF(i == max)
"NO" 출력
종료
종료
Else
Loop While (i < max)
data = 'a' + rand() % 2
data 출력
i 증가
종료
"NO" 출력
End
종료C++ 구현 코드
아래 코드는 난수로 'a' 또는 'b' 문자열을 생성한 뒤, DFA의 논리에 따라 해당 문자열이 조건을 만족하는지 판별합니다.
#include <iostream>
#include <time.h>
using namespace std;
int main() {
// 난수 생성을 위한 시드 설정
srand(time(0));
int max = 1 + rand() % 15;
int i = 0;
while (i < max) {
char data = 'a' + rand() % 2;
cout << data << " ";
i++;
if (data == 'a') {
if (i == max)
cout << "YES\n";
while (i < max) {
data = 'a' + rand() % 2;
cout << data << " ";
i++;
if (data == 'a' && i == max) {
cout << "\nYES\n";
} else if (i == max) {
cout << "\nNO\n";
}
}
} else {
while (i < max) {
data = 'a' + rand() % 2;
cout << data << " ";
i++;
}
cout << "\nNO\n";
}
}
return 0;
}실행 결과
b b a b a b a b b b b b NO
위 실행 결과에서 볼 수 있듯이, 생성된 문자열이 'b'로 끝났기 때문에 프로그램은 NO를 출력합니다. 반대로 문자열이 'a'로 시작하고 'a'로 끝난다면 DFA는 최종 상태에 도달하여 YES를 출력하게 됩니다.