[이산수학] 오토마타 / 형식 언어 / 문법

컴퓨터 수학적 모델 오토마타와 형식 언어, 문법에 대해 알아보자

오토마타, 형식 언어, 문법에 관한 연구는 매우 추상적임

컴파일러, 문서 편집기, 엘리베이터 등 다양한 분야에 응용이 됨

오토마타란?

오토마타

디지털 컴퓨터의 수학적 모델인 **‘오토마톤’**의 복수형으로 **‘자동기계 장치’**라는 뜻

일반적으로 입력, 출력, 저장, 제어 장치를 가지는 컴퓨터의 이론적 메커니즘

단순한 오토마타로는 고대 이집트의 모래시계부터 현대의 뻐꾸기 시계도 포함

실생활에서 만나는 오타마타

이론적인 자판기 오토마타

50원과 100원짜리 동전을 투입가능하고 투입한 돈이 300원이나 그 이상일때 커피나 음료수를 내주고 거스름돈을 돌려주지 않는 가정 → 투입 액수에 따라 상태가 변화 동전 투입 시 액수가 변화해야하며 300원 이상의 액수가 있을 경우 음료수를 출력해야함

오토마타의 특성

입력 데이터를 읽을 수 있는 기능을 가짐 (입력 장치)

특정 형태의 출력 기능을 가짐 (출력 장치)

무한개의 셀들로 이루어진 임시 저장 장치를 가질 수 있음 (저장 장치)

오토마타의 유한개의 내부 장태를 제어할 수 있는 제어 장치를 가짐 (제어 장치)

결정적/비결정적 오토마타

오토마타는 이산적인 시간 단위로 작동을 기본으로 함

어느 특정 시간에 제어 장치는 특정 상태에 놓여있음

입력 기능은 입력 파일상의 특정한 심볼을 읽음

제어 장치의 다음 상태는 전이 함수에 의해 결정

전이 함수는 현재의 제어 상태, 입력 심볼, 임시 저장 장치 내의 정보들에 의해 결정

→ 결정적 오토마타는 전이에 의한 다음 상태가 현재의 형상에 따라 유일하게 결정되는 오토마타

→ 비결정적 오토마타는 현재의 형상에서 2가지 이상의 이동도 가능한 오토마타

인식기/트랜스듀서

오토마타는 출력 여부에 따라 나누어짐

→ 인식기는 주어진 입력에 대해 인식하거나 기각할 수 있는 기능만을 가짐

→ 트랜스듀서는 인식과 기각의 기능 외에 출력도 가능한 오토마타 모델

유한 상태 시스템

오토마타 학습의 필요성

전산학이나 전자공학의 기본적인 개념과 원리를 제공하고 여러 가지 응용 분야에 적용

하드웨어나 소프트웨어 각 분야에 대한 직관을 넓히고 포괄적인 통찰력을 제공

컴파일러와 프로그래밍 언어를 정확하게 이해하기 위해 이론의 이해가 필수적

추상적 모델의 개념적 이해로 복잡한 현상을 간략하고 정확하게 추상화

유한 상태 시스템 (Finite State Machine : FSM)

유한 상태 시스템의 응용

1. 엘리베이터의 제어 과거에 요청한 모든 요구들을 기억하지 않고 아직 이루어지지 않은 현재의 요청에 대해서만 기억하는 유한 상태 시스템
2. 컴퓨터의 논리 회로 논리회로는 통상 0과 1로 표시되는 2가지 조건 중 하나의 사태인 유한 개의 게이트들의 집합으로 구성
3. 문서 편집기와 어휘 분석기 문서 편집기는 입력 추가 시 상태 변화 / 어휘 분석기는 컴퓨터 프로그램에서 심볼들을 차례로 읽어 대응 → 유한개의 정보를 기억하는 유한 상태 시스템

유한 오토마타

유한 오토마타 (Finite Automata : FA)

이산적인 입력과 출력을 가지는 시스템 수학적 모형

유한 개의 내부 상태를 가지며 시스템은 다음에 들어올 입력에 대한 시스템의 행동을 결정하는 데 피룡한 과거의 정보들을 요약

임시 저장 장치를 가지지 않으며 따라서 작동 과정에서 정보를 기억하는 데 상당한 제약을 가짐

유한 제어 (Finite Control)

유한 오토마타의 입력과 상태들을 제어

유한 오토마타는 여러 종류의 오토마타들 중에서 가장 단순한 형태로서 유한 제어를 가진 유한 오토마타를 나타냄

정규 언어

유한 오토마타는 전이 방법에 따라 결정적 유한 오토마타와 비결정적 유한 오토마타로 구분

2개가 기능에 있어서는 똑같으나 유한 오토 마타에 대응하는 언어

결정적 유한 오토마타

5개의 순서쌍으로 이루어짐

• 상태들의 유한 집합
• 입력 알파벳
• 전이 함수
• 시작 상태
• 최종 상태의 집합

유한 오토마타의 응용

C언어에서의 변수를 만드는 방법

→ 각 변수는 하나의 문자로 시작, 그 이후는 숫자와 문자 혼용가능

형식 언어와 문법

3가지 개념

언어, 문법, 오토마타로 해당 3가지 상호 간에 깊은 관련성을 가지고 있기 때문에 각각의 개념을 파악하고 그들 간의 관계를 탐구하는 것은 매우 중요

언어

우리가 일상생활에서 자주 사용하는 자연어와 오토마타를 이용하여 만들어지는 이론적인 형식 언어로 나뉨

알파벳은 유한개의 공집합이 아닌 심볼들의 집합으로 스트링이 만들어짐

펠린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 스트링을 말함

스트링에서의 연산

• 연결
• 역
• 길이
• 반복
• 언어와 문장
• 언어에서의 연산

문법

자연어에서의 문법을 일컬으며 컴퓨터에서 사용하기에 애매함을 배제하는 방법을 정의해야함

어떤 문장이 제대로 작성되었는지의 여부를 판정하는 기준

구체적인 규칙에 의해 정의되기에 파스트리의 형태로 나타낼 수 있음

튜링머신 모델

각 프로시저는 유한하게 기술될 수 있어야하며

프로시저는 기계적으로 수행되는 이산적인 단계들로 이루어짐

튜링머신은 이러한 조건을 만족하는 모델로 7개의 쌍으로 이루어진다

• 상태들의 유한 집합
• 허용되는 테이프 심볼들의 유한 집합
• 허용되는 테이프 심볼들의 유한 집합에 속하는 블랭크
• 입력 심볼의 집합
• 다음 동작 함수
• 시작 상태
• 최종 상태

임시 기억 장치가 테이프인 오토마타

이처럼 오토마타를 통해 형식 언어와 문법을 알아볼 수 있었음