유한오토마타
유한 오토마타(Finite Automata, FA)의 정의는 다음과 같습니다.
유한 오토마타는 상태의 개수가 유한하고, 입력에 따라 상태 전이를 수행하면서 입력 문자열을 수락(accept)하거나 거부(reject)하는 추상적 계산 모델입니다.
수학적으로 다음과 같이 정의됩니다.
유한 오토마타 M은 5-튜플로 표현됩니다.
M = (Q, Σ, δ, q₀, F)
여기서,
Q : 유한한 상태의 집합 (states)
Σ : 유한한 입력 알파벳(input alphabet)
δ : 상태전이함수(transition function)
결정적 유한 오토마타(DFA): δ : Q × Σ → Q
비결정적 유한 오토마타(NFA): δ : Q × Σ → Q의 멱집합
q₀ : 초기 상태(start state), q₀ ∈ Q
F : 수락 상태들의 집합(final states), F ⊆ Q
유한 오토마타의 종류
결정적 유한 오토마타(DFA)
상태와 입력에 따라 전이할 다음 상태가 반드시 하나로 결정됨.
비결정적 유한 오토마타(NFA)
같은 상태와 입력에서 다음 상태가 하나 이상이거나 없을 수도 있음. NFA와 DFA는 같은 표현력을 가지며, 상호 변환이 가능함.
특징 및 응용
유한 오토마타는 정규 언어(regular language)를 인식합니다.
컴파일러의 어휘 분석기(Lexical analyzer) 구현, 패턴 인식(pattern recognition), 문자열 검색 등에 사용됩니다.
수락 상태(Accepting State) 의 정의는 다음과 같습니다.
유한 오토마타에서 수락 상태란 오토마타가 입력 문자열을 읽고 난 후 마지막으로 도착한 상태로, 그 상태가 '수락 상태'에 속하면 오토마타는 그 입력 문자열을 수락(accept) 했다고 표현합니다.
즉, 오토마타가 입력 문자열을 모두 처리한 뒤 최종적으로 도달한 상태가 수락 상태의 집합(보통 F로 표현) 내에 있다면, 해당 문자열은 그 오토마타가 정의하는 언어에 포함됩니다.
만약 최종 상태가 수락 상태가 아니면, 입력 문자열은 거부(reject)됩니다.
수락 상태는 하나 이상 존재할 수 있습니다.
수락 상태는 최종 상태(final state)라고도 부릅니다.
쉽게 말하면, 수락 상태는 특정 문자열이 오토마타에 의해 인정(허용)되었음을 나타내는 상태입니다.
근데 굳이 필요한가? 처음부터 규칙에 맞게 쓰면 되지
맞습니다. 이론적으로는 처음부터 규칙에 맞게 문자열을 생성하면 굳이 오토마타가 수락 여부를 판단할 필요가 없습니다.
하지만 유한 오토마타를 사용하는 이유는 실제 상황에서 다음과 같은 이유 때문입니다.
현실적인 활용 상황:
입력 문자열이 미리 정해진 규칙에 맞는지 모르는 상황
예: 사용자가 입력한 비밀번호나 이메일 형식 검사
컴파일러나 파서(parser)에서 입력의 유효성 검증
예: 프로그래밍 언어의 문법을 체크하는 어휘 분석기
이미 존재하는 수많은 데이터 중 원하는 규칙의 문자열만 골라낼 때
예: 데이터베이스나 텍스트 파일에서 특정 패턴을 찾을 때
즉, 처음부터 규칙대로만 입력 문자열이 들어오는 이상적인 상황이라면 굳이 오토마타가 필요하지 않겠지만, 실제로는 규칙에 맞는지 아닌지를 확인하는 과정이 매우 중요하기 때문에 오토마타와 같은 "판정 알고리즘"이 필요합니다.
이런 이유로 현실적으로는 오토마타를 통해 언어에 속하는지 여부를 자동으로 판별하는 것이 유용합니다.
좋은 질문입니다. 요점을 정리하자면:
1. 전이 함수의 "내용"이란 실제로 무엇인가?
전이 함수 δ의 "내용"은 오토마타를 설계할 때 사람이 직접 지정해주는 규칙입니다.
즉, 오토마타는 어떤 언어를 인식하고 싶은지를 설계자가 먼저 결정하고, 그에 맞게 상태 전이 δ를 정의하는 것입니다.
예를 들어, 다음과 같은 언어를 인식하는 DFA를 만들고 싶다고 해봅시다:
> 짝수 개의 0을 포함하는 문자열을 인식하는 DFA (Σ = {0,1})
설계자는 다음과 같은 전이 함수를 정의합니다:
q0: 0의 개수가 짝수일 때의 상태 (시작 상태이자 수락 상태)
q1: 0의 개수가 홀수일 때의 상태
여기서 이 표 자체가 전이 함수의 내용입니다.
즉, 전이 함수는 "없다"기보다는, 오토마타를 설계할 때 사람이 정의해야 하는 핵심 정보입니다.
알고리즘은 그걸 기반으로 "판단"하는 것이 아니라 그냥 따라가는 것이고요.
---
2. 요약
전이 함수는 오토마타에 주어져야 합니다. (입력의 일부임)
그것이 없다면 오토마타는 아무것도 판단할 수 없습니다.
알고리즘은 δ가 존재한다는 전제 하에 작동합니다.
따라서 오토마타는 "판단하는 기계"가 아니라, "규칙(δ)을 따라 입력을 해석하는 기계"입니다.
즉, 전이 함수의 내용이 없다면 오토마타는 의미가 없습니다.
전이 함수 = 오토마타의 두뇌이자 전부입니다.