1. 오토마타
오토마타 스스로 움직이는 기계, 컴퓨터 : 유한상태 오토마타
튜링머신 (Turing machine) 메모리테이프, 헤드, 상태기록 레지스터, 유한테이블 (명세된 명령어, 별도의 인풋은 없음)
형식언어 프로그래밍 언어들의 일반적인 특성을 추상화한 개념,
형식문법 프로그래밍 언어의 생성규칙을 추상화한 개념
촘스키 계층
(1) 유한 오토마타
(2) 결정적 유한 오토마타 (deterministic) FA
출력기호와 출력함수가 없으며 수락상태가 있는 오토마타
(3) 비결정적 유한 오토마타 (nondeterministic) FA
입력이 없는 경우 상태를 전이하는 오토마타 ( ε 전이 : 입력없이 상태를 전이 )
2. 마르코프 연쇄
(1) 마르코프 연쇄
마르코프 성질을 만족하는 이산확률과정
유한 오토마타의 특수한 형태, 시간에 따른 상태의 변화(상태전이)를 확률로 표현함
이산확률과정 (이산적 시간 n에서 오토마타의 상태)
(2)마르코프 성질
특정 단계의 확률이 바로 앞단계의 상태에만 영향을 받고, 그 이전의 상태와는 연관성이 없는 성질
(3) n단계 전이확률
채프만 콜모고로프 방정식 ( n단계 전이확률은 행렬의 n승)
▷ 마르코프 연쇄 (페이지 랭크 예제)
3. 형식언어와 형식문법
(1) 형식언어
유한한 기호들의 집합을 이용해 만들어지는 유한한 문자열의 집합
(2) 형식문법
형식 언어의 문자열들을 생성해 낼수 있는 유한개의 규칙
(3) 알파벳과 문자열
정의 공집합이 아닌 기호들의 유한집합 ∑을 알파벳이라고 함
알파벳에 포함된 기호들의 유한한 순서쌍을 문자열이라고 함
문자열 중에서 아무런 기호도 포함하지 않는 문자열을 공문자열(empty string)이라고 하고 λ로 표기
예) ∑ = {0,1} ⇨ λ, 0, 1, 10, 010, 0001, 10010 등
(4) ∑ⁿ , ∑⁺, ∑＊, 언어 (language) ( λ포함 여부구분 )
▷ 언어 정의에 대한 예제
(5) 언어의 연산 및 예제
(6) 구구조 문법 (phrase-structure grammar)
4개 원소의 순서쌍으로 정의되는 G = ( V, T, P, S)
단말기호는 (T, 끝기호), 생성규칙, 변수, 시작기호등으로 표시
(7) 형식문법에 의해 생성된 언어
형식문법에서 생성 규칙은 하나의 문자열을 다른 문자열로 변환
문법에서 정의된 생성규칙을 이용하여 생성되는 문자열의 집합을 해당 문법에 의해 생성된 언어라고 부름
▷ 예제
(8) Chomsky의 4가지 문법형태
'스터디 > 이산수학' 카테고리의 다른 글
| 이산수학 - 정수론 (0) | 2023.06.11 |
|---|---|
| 이산수학 - 조합이론 (2) | 2023.06.11 |
| 이산수학 - Tree (1) | 2023.06.11 |
| 이산수학 - 그래프 (1) | 2023.06.11 |
| 이산수학 - 함수 부울대수 (0) | 2023.06.11 |