[이산수학#14] 오토마타와 형식 언어

1. 오토마타

오토마타 : 자동장치, 스스로 움직이는 기계 ex) 컴퓨터 : 유한상태 오토마타

튜링머신 : 인간 사고과정을 구현하는 오토마타, 컴퓨터의 수학적 모델

형식언어 : 프로그래밍 언어들의 일반적인 특성들을 추상화

형식문법 : 프로그래밍 언어의 생성 규칙을 추상화

 

 

2. 유한 오토마타

유한 오토마타	결정적 유한 오토마타
방향 그래프 -> 상태 그래프 -> 상태도 -> 상태전이도 상태 그래프 - 상태 : 원 - 전이 : 그래프 - 입력값과 출력값 : 화살표 위에 표시	비결정적 유한 오토마타

3. 마르코프 연쇄

마르코프 연쇄 : 마르코프 성질을 지닌 이산확률과정

- 유한 오토마타의 특수한 형태

- 시간에 따른 상태의 변화를 확률로 표현

 

이산확률과정

- 𝑿n : 확률변수

- (𝑿𝟏,𝑿𝟐, … ,𝑿𝒏, … ) : 이산학률과정, 이산적인 시간 흐름에서 순차적으로 관측되는 확률변수의 모임

 

마르코프 성질 : 무기억성, 미래 상태는 오직 현재 상태에만 영향을 받는다는 성질

정상 마르코프 연쇄 : 전이 확률의 불변성, 시간의 변화에 무관하다는 성질

전이확률 : 상태 집합에서 현재 상태에서 다음 상태로 전이될 확률

 

표현방법 : 전이확률행렬, 상태전이도

전이확률행렬 : 행렬을 나타내는 것, 𝑷 = (𝑷𝒊𝒋)

상태전이도 : 상태와 상태전이확률을 도식화, 유한 오토마타를 표현하는 상태그래프와 기본적으로 동일

 

n단계 전이확률 : 채프만 콜모고로프 방정식, 페이지랭크

채프만 콜모고로프 방정식 :

현재 [𝒕 = 𝒎]상태 i 에서 n 단계 이후 [𝒕 = 𝒎 + 𝒏] 에 상태가 j 가 될 확률

페이지 랭크 : 페이지에 방문학 확률

 

4. 형식 언어와 형식 문법

형식언어 : 유한한 기호들의 집합을 이용해 만들어지는 문자열의 집합 ex) 알파벳과 문자열, 언어의 연산

형식문법 : 형식 언어의 문자열들을 생성해 낼 수 있는 유한개의 규칙 ex)구구조 문법, 유도

 

Chomsky 계층

무제약 문법 : 제 0 유형, 생성 규칙이 𝜶 → 𝜷, 단 𝜶 ∈ (𝑽 ∪ 𝑻) + ,𝜷 ∈ (𝑽 ∪ 𝑻) ∗

문맥 의존 문법 : 제1유형, 𝜶 → 𝜷, 단 𝜶,𝜷 ∈ (𝑽 ∪ 𝑻) + , |𝜶| ≤ |𝜷|, 생성의 우변이 좌변보다 길이가 작을 수  X

문맥 자유 문법 : 제2유형, 𝑨 → 𝜷, 단 𝑨 ∈ 𝑽, 𝜷 ∈ (𝑽 ∪ 𝑻) ∗

정규 문법 : 제3유형, 𝑨 → 𝜶 혹은 𝑨 → 𝜶𝑩, 단 𝑨, 𝑩 ∈ 𝑽, 𝜶 ∈ 𝑻 ∗ ex) 우선형 문법, 좌선형 문법