선형유한 자동 기계(Linear Bounded Automaton, LBA)는 형식 언어 이론에서 사용되는 추상 기계 모델 중 하나로, 튜링 기계의 일종이다. 이는 입력 문자열의 길이에 비례하는(선형적으로 제한된) 양의 테이프 공간만 사용하는 튜링 기계로 정의된다.
구성 및 작동 원리
선형유한 자동 기계는 기본적으로 튜링 기계와 동일한 구성 요소를 갖는다: 유한 상태 제어기(finite state control), 읽고 쓰기가 가능한 헤드(read/write head), 그리고 테이프(tape)이다. 가장 큰 차이점은 테이프의 길이가 입력 문자열의 길이에 따라 제한된다는 것이다. 만약 입력 문자열의 길이가 $n$이라면, LBA는 $c \cdot n$ 만큼의 테이프 셀만 사용할 수 있으며, 여기서 $c$는 고정된 상수이다. 테이프의 양 끝에는 특별한 좌우 마커가 있어 기계가 이 경계를 넘어가지 않도록 한다.
LBA는 입력 문자열을 테이프에 기록한 상태에서 시작하며, 유한 상태 제어기의 지시에 따라 헤드를 이동시키고 테이프의 내용을 읽거나 쓸 수 있다. 테이프의 내용이 변경될 수 있다는 점에서 푸시다운 자동 기계(Pushdown Automaton)와 구별되며, 테이프 길이가 무한하지 않다는 점에서 일반적인 튜링 기계와 차이가 있다.
촘스키 위계에서의 위치
선형유한 자동 기계는 촘스키 위계(Chomsky hierarchy)에서 문맥 의존 언어(Context-Sensitive Language, CSL)의 정확한 인식기(recognizer)이다. 즉, LBA가 인식할 수 있는 모든 언어는 문맥 의존 언어이며, 모든 문맥 의존 언어는 LBA에 의해 인식될 수 있다. 이는 문맥 의존 언어가 촘스키 위계의 유형 1(Type 1)에 해당한다는 것을 의미한다.
결정적 LBA 문제 (LBA Problem)
비결정적 선형유한 자동 기계(Non-deterministic LBA, NLBA)는 문맥 의존 언어를 정확히 인식하는 것으로 알려져 있다. 하지만 결정적 선형유한 자동 기계(Deterministic LBA, DLBA)가 비결정적 LBA와 동일한 클래스의 언어를 인식하는지 여부는 계산 복잡도 이론의 중요한 미해결 문제 중 하나이다. 이를 'LBA 문제' 또는 '결정적 LBA 문제'라고 부르며, P=NP 문제와 유사하게 결정적 모델과 비결정적 모델의 계산 능력 차이에 대한 근본적인 질문을 담고 있다.
중요성
LBA는 튜링 기계에 비해 계산 능력이 제한적이지만, 공간 복잡도(space complexity)를 연구하는 데 있어 중요한 모델이다. 특히, 입력 크기에 비례하는 선형 공간 제한은 복잡도 클래스 NSPACE(n) (비결정적 선형 공간)과 DSPACE(n) (결정적 선형 공간)의 연구에 기반이 된다. LBA는 이론 컴퓨터 과학에서 언어와 기계 간의 관계, 그리고 계산 자원의 제한이 계산 능력에 미치는 영향을 탐구하는 데 필수적인 도구이다.