오토마타와 형식언어

중간고사 정리

 

 

오토마타 개념

오토마타 = 모든 장치들의 작동 원리

ex.컴퓨터, 자판기, 세탁기, 물시계 등 모두 오토마타.

오토마타가 뭐지? → 입력을 받아들여, 정의된 상태 전이 규칙에 따라 상태를 변경하고, 특정 상태에 도달하면 계산을 멈추는 추상적인 기계

오토마타 이론

• 컴퓨터 과학에서 계산의 추상 모델을 연구하는 분야
• 오토마타는 입력을 받아들여, 정의된 상태 전이 규칙에 따라 상태를 변경하고, 특정 상태에 도달하면 계산을 멈추는 추상적인 기계를 의미
• 이론은 다양한 계산 문제를 해결하기 위한 1) 알고리즘과 2) 프로세스의 이해를 돕는 기초적 틀 제공.

오토마타, 형식 언어, 문법?

• 이에 대한 언어는 매우 추상적 특성 가짐
• 오토마타, 형식 언어, 문법은 각각 뭐고, 어떤 관계를 가지지?

오토마타 : 입력 받아 정의된 상태 전이 규칙에 따라 상태 변경하고, 특정 상태 도달하면 계산 멈추는 ‘기계’ 이론적 기계. 문법은 문법이고 형식 언어는 언어이고… 무슨 관계지?

• 이론적 계산 모델인 오토마타 중 유한 오토마타는 컴파일러의 어휘분석 수행에 결정적 역할
• 3가지는 상호 밀접 관계. 왜? 여러 컴퓨터 프로그램 언어들이 정해진 문법에 따른 형식 언어에 기반 두고 만들어졌기에. 문법이 있고 형식 언어가 있는 거? 그럼 오토마타는?
• 튜링머신은 현재의 디지털 컴퓨터의 역량과 대등한 계산 모델임.

오토마타 정의

• ‘디지털 컴퓨터의 수학적 모델’ 오토마톤의 복수형
• 자동기계장치 란 뜻 가짐
• 입력 장치, 출력장치, 저장 장치, 제어 장치 가짐

오토마타의 특성

• 입력 데이터 읽을 수 있는 입력 기능 가짐
• 입력 데이터는 입력 파일에 쓰여져 있는 알파벳상의 스트링들로 이루어져 있는데 입력 파일은 네모꼴의 셀들로 이루어져 있으며 각 셀에는 오직 하나의 심볼만 존재함.
• 특정 형태의 출력 기능 가짐. 0이나 1의 출력 생성하며 인식 또는 기각의 출력도 생성
• 오토마타는 무한개의 셀들로 이루어진 임시 저장장치 가짐. 각 셀은 하나의 심볼만 가질 수 있는데 오토마타는 작동에 따라 셀들의 내용을 읽어내거나 변경할 수 있음.
• 유한 개의 내부 상태 제어할 수 있는 제어 장치 가짐. 제어에 따라 상태가 변화될 수 있음.

뭘 저장하지?

오토마타의 기본 개념

• 오토마타는 이산적인 시간단위로 작동됨을 기본 가정함.
• 어느 특정 시각에 제어 장치는 특정한 상태에 놓여 있음. 제어장치 - cpu
• 제어 장치의 다음 상태는 전이 함수에 의해 결정됨
• 전이 함수는 현재의 제어 상태, 입력 심볼, 임시 저장 장치 내의 정보들에 의해 결정됨.

오토마타의 기본 구성 요소

1. 상태 : 오토마타의 현재 조건이나 구성. 상태는 유한, 오토마타가 어떤 입력 받았을 때 다음에 어떤 동작 할 지 결정하는 데 사용됨.
2. 입력 알파벳
3. 전이 함수
4. 시작 상태 : 오토마타가 계산 시작하는 상태
5. 종료 상태 : 입력 문자열 받아들이고 계산 마친 상태들의 집합.

오토마타 주요 유형

1. 유한 오토마타 : 가장 단순한 형태의 오토마타. 유한한 수의 상태를 가짐.

결정적 유한 오토마타와 비결정적 유한 오토마타로 나뉨.

1. 푸시다운 오토마타 : 스택 사용해 무한한 양의 메모리 모델링 가능. 컨텍스트-프리 언어 인식에 사용
2. 튜링 기계 : 무한한 테이프와 읽기/쓰기 머리 가진 가상의 기계. 모든 계산 가능한 문제 해결할 수 있는 이론적 모델.

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

결정적 : 전이에 의한 다음 상태가 현재의 형상에 따라 유일하게 결정됨

비결정적 : 현재의 형상에가 2가지 이상의 이동도 가능. → 가능한 이동의 집합만 예측할 수 있음.

출력 여부에 따른 오토마타

• 인식기 : 주어진 입력에 대해 인식하거나 기각할 수 있는 기능만 가짐
• 트랜스듀서 : ‘밀리’ 처럼 인식, 기각 외에 출력도 할 수 있는 오토마타.

음료 자판기마냥 300원 이상이면 음료수 내주고 상태 전이 계속 하니, 트랜스듀서임.

유한 상태 시스템 (Finite state machine)

• FSM 은 유한개의 상태 가진 오토마타
• 엘리베이터의 제어 : 과거의 모든 요청 기억 X
• 컴퓨터
• 컴퓨터의 제어 장치와 같은 논리 회로 : 0과 1로 표시되는 2가지 조건 중 하나의 상태인 유한개의 게이트들의 집합.
• 문서 편집기와 어휘 분석기에도 적용됨.

유한 오토마타

• 이산적인 입력, 출력 가지는 시스템의 수학적 모형
• 유한한 개수의 내부 상태 가짐. 시스템의 상태는 다음에 들어올 입력에 대한 시스템의 행동을 결정하는데 필요한 과거의 정보들 요약.
• 인식기로서의 유한 오토마타를 고찰
• 주요 특징은 - 임시 저장장치 가지지 않는다는 점과, 입력테이프는 단지 읽힐 수만 있으며 내용 변경불가.
• 유한 오토마타의 기능은 작동 과정에서 정보를 기억하는 데 있어서 상당한 제약을 받게 됨.
• 어떤 알파벳 시그마로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로, 시스템에서 변화할 수 있는 상태가 유한개인 것.
• 플립플롭을 비롯한 컴퓨터 고안물들, 형식언어의 연구, 컴파일러 등에 유용하게 쓰임.
• 어휘분석기는 대표적인 것
• 상태 전이도와 같이 비형식적으로 표현한느 방법 많이 씀.
• 기능적인 측면에서 인식기와 변환기로 구분

인식기 - 입력된 결과에 대해 오토마타는 인식, 기각 등을 표시하는 이진 기호를 출력

언어 변환기- 주어진 입력에 대응하는 새로운 문자열을 출력

변환기에는 - 상태에 빠른 출력을 내는 moore 기계와 전이에 따른 출력을 내는 mealy 기계 등이 있다.

상태전이도

• 오토마타의 각 상태를 노드로 표현
• 이동함수 시그마(q,a) = p 출발 :q, 간선 a 따라 p에 도착.
• 최종 상태 : 이중원. 시작 상태는 시작 간선으로 표시하는 유향그래프 →

유한 제어

• 유한 오토마타의 입력과 상태들을 제어함
• 유한 오토마타는 오토마타 중 가장 단순한 형태로 입력과 유한 제어를 가진 유한 오토마타를 나타냄.

유한 오토마타의 전이함수

• 유한 오토마타 : 유한한 상태들 집합 + 전이함수들의 집합
• 전이 = 알파벳 E 로 부터 선택된 입력 심볼에 의해 생기는 상태에서 상태로의 변화
• 입력에 따라 상태 항상 변할 수 있으며, 원래의 상태로 다시 돌아가는 전이도 있을 수 있음.

유한 오토마타 시작 상태, 최종 상태

• q zero : 시작 상태 → 여기서 오토마타 시작됨
• 최종상태, 인식상태 - 이중의 서클로 표시

전이 다이어그램

• 각 노드 = 유한 오토마타의 상태에 해당
• 입력 스트링 x에 대해 시작 상태 → 최종 상태 가는 경로 존재한다면 유한 오토마타는 스트링 x를 인식하게 됨.

정규 언어

• 유한 오토마타는 전이 방법에 따라 결정적 유한 오토마타 , 비결정적 유한 오토마타로 구분.
• 2개가 기능에 있어서는 서로 동치 + 유한 오토마타에 대응하는 언어임.

결정적 유한 오토마타의 동작

• 시작상태 q0. 유한 제어는 입력 스트링의 가장 왼쪽에 있는 심볼 가리킴
• 작동에 따라 입력 장치에서 한 심볼씩 오른쪽으로 이동하면서 상태가 바뀜
• 스트링 모두 읽고 DFA가 최종상태에 있으면 그 스트링이 인식되고, 그렇지 않으면 기각된다.
• 각 단계에서 하나씩의 심볼만 읽을 수 있다.

출력이 없는 유한 오토마타 (DFA)

• 입력 스트링을 모두 읽고 나서도 최종 상태에 도달 여부로 인식 or 기각함.

출력이 있는 유한 오토마타 (DFA)

Mod 3 카운터

유한 오토마타의 응용

2장 _ 계산이론

Computability (계산 가능성)

-튜링 기계, 할팅 문제, 재귀 함수 등의 개념 포함.

Complexity. 복잡도. : 이 부분 모르겠음.

정보 이론

수학관련.

powerset : 멱집합.

the powerset of S

S의 모든 부분집합의 집합.

Cartesian Product (of A and B)

카티션 곱 : 곱집합.

동치관계

• 집합 A에 대한 등가 관계는 재귀적, 대칭적, 전이적인 A에 대한 관계
• Reflexivity : 모든 a → aRa
• Symmetry : 모든 a , b → if aRb → bRa
• Transitivity : 모든 a, b, c → if aRb, bRc → aRc

3장 _ 형식언어 개념

꺄 > < 형식 언어와 문법

오토마타 이론에서 중요한 3가지 개념 : 언어, 문법, 오토마타

(1) 언어

팰린드롬. - 앞에서 읽으나 뒤에서 읽으나 동일.

스트링 연산 : 1) 연결 concatenation 2) 역 3) 스트링의 길이 |w| 절대값 써서 나타냄.

주어진 스트링이 어떤 심볼도 없을 땐 공 스트링 → 람다. y 뒤집은거처럼 생긴 것

1. 스트링 반복 w^n. w^0 = 람다
2. 시그마 스타 : 시그마 상에서의 심볼들의 결합에서 만들어지는 모든 스트링 집합. 람다항상 포함. 시그마 데거 : 람다 제거한 것.

6)언어와 문장

언어 L : 시그마 스타의 부분집합. 대문자 L.

1. 언어에서의 연산 : 언어는 단어로 이루어진 집합이므로… 합, 교, 차 등 집합의 일반적 연산 가능. 여집합. 연결 등의 연산도 가능

형식 언어 개념

• exact 수학적 모델 사용해 정의된 문자열의 집합. 알파벳이라고 하는 미리 정의된 기호들의 집합 사용하여 구성.
• 여기서 수학적 모델이 문법말하는 건강.
• 추론 규칙 or 생성 규칙에 기반해 이뤄짐.
• 컴퓨터 과학, 컴파일러의 구성, 자연어 처리, 인공지능, 계산 이론에서 중요한 역할을 함.

형식 언어의 분류 체계

• 추론 계층/구조 _ 촘스키 구조

1. 유한상태 오모마타에 의해 인식될 수 있는 정규 언어
2. 푸시다운 오토마타 - 컨텍스트 프리 언어
3. 선형 유계 오토마타 - 컨텍스트 - 센시티브 언어
4. 투링 기계 - 재귀적으로 열거 가능한 언어

형식언어의 구성 요소

1. 알파벳
2. 문자열
3. 언어

결론 : 특정 규칙, 패턴따라 문자열 생성 → 규칙성 가진 문자열의 집합이 형식 언어

형식 언어 정의들

접두사 : 문자열 w = uv 일 때, u를 문자열 w의 접두사

진접두사 : u ≠ e

접미사 : 문자열 w = uv일 때 v를 문자열 w의 접미사 (뒤에 오는 것)

문자열 = w = house

접두사 : e, h, ho, hou, hous, house

접미사 : house, ouse, use, se, e, e

문법

(2) 컴퓨터에서 쓰이는 문법에는 애매성 배제 되어야. 일정한 규칙 따라 엄밀하게 정의되어야 함.

형식언어는 그냥 컴퓨터에서 쓰는 언어라고 보면 되겠다. 일정한 규칙을 따르는.

• 문법 : 베커스 나우어 표기법 (BNF) , 푸시다운 오토마타에 의한 문맥자유 문법으로 구별

문법의 정의

• 문장이 제대로 작성되었는지 여부 판정 기준이 됨.
• 특정 형식언어 생성하기 위한 규칙의 집합 : 문법은 어떤 문자열이 특정 형식 언언어에 속하는지 결정하는데 사용.
• 문법의 구성요소

→ N : 비터미널 기호들의 유한한 집합. 교체가능한 중간기호

→ 시그마 : 터미널 기호들의 유한한 집합. 언어에서 최종적으로 나타나는 문자들

→ P : 생산 규칙의 집합.

→ S : 시작 기호. N 에 속하는 특정 비터미널 기호로 문법에 의해 생성된 문자열의 생성이 시작되는 지점임.

문법의 정의

인식기 : 언어는 인식기에 의해 인식

type 0 : 무제약 문법 : 재귀 열거 언어 : 튜링 기계

type 1 : 문맥인식 문법 : 문맥인식 언어 : 선형한계 오토마타

type 2 : 문맥자유 문법 : 문맥자유 언어 : 푸시다운 오토마타

type 3 : 정규 문법 : 정규 언어 : 유한 오토마타

정의 1. 문법 G = (Vn, Vt, P, S) 정의

생성 규칙 P

알파 → 베타. 알파는 V+에 포함, 엡실론 안됨. 베타 → V* 엡실론 가능.

형식 언어 이론에서 자주 인용되는 언어들

1. 단순 매칭 언어 : CFL

Lm = {a^n b^n | n ≥ 0}

1. 중복 매칭 언어 : CSL

Ldm =

1. 좌우대칭언어

ww^R

1. 회문언어

ex. 대학생학대

1. 괄호 언어