오늘 한 일
계산이론 강의
이산수학 강의
해커톤 예선 자료 끝
과제
봉사 자료 확인
복습
내일 할 일
봉사 준비 + 봉사
이산수학 강의
계산이론 강의
과제
복습
---------------------------------------------
람다 : null String
|w| : 스트링 w의 길이
uv에서
접두사 u
접미사 v
xuy에서
부분 스트링 u
시그마* : closure. 시그마 기호를 0번 이상 연결하여 만든 스트링의 집합
시그마+ : 시그마 기호를 1번 이상 연결하여 만든 스트링의 집합.
언어 : 시그마의 클로저의 부분집합
G = (V, T, S, P)
V = 변수 = N
T = 단말 심벌. 객체들의 집합 = 시그마
S = V에 속함. 시작 변수
P = 생성 규칙
L(G1) = L(G2) : 동치
a -> b : a를 b로 바꿀 수 있다.
xay => xby : a -> b를 이용하여 xay로부터 xby를 유도한다.
=> : 직접(1번에) 유도
*=> : 여러번(0번 이상)에 유도
촘스키의 분류.
Type 3 : 정규 문법
a)우선형 : A -> x B 또는 A -> x
b)좌선형 : A -> B x 또는 A -> x
튜링 기계
Type 2 : 문맥자유 문법
A -> b
선형한계 오토마타
Type 1 : 문맥연관 문법
a -> b (단, S -> 람다는 허용)
푸시다운 오토마타
무제한 문법
a -> b
유한 오토마타
오토마타 : 컴퓨터에 대한 추상적 모델.
입력 파일 : 입력 스트링 들어 있어, 입력시 기호를 하나씩 읽어들임
메모리(stack) : 특정 기호를 기억. (푸시다운 오토마타에만 존재)
상태 전이함수
출력 : accept/reject(실행이 된다 / 안 된다) 혹은 string (string으로 출력한다)
비결정적 : 0개 이상의 상태로 전이. 상태 전이가 될 수도, 여러개로 될 수도 있다는 뜻
결정적 : 많아야 1개 상태로 전이
인식기 : 입력 - 오토마타, 푸시다운 오토마타. 출력 - accept/reject
변환기 : 입력 - 밀리기계, 무어기계. 출력 - string
무어 기계 : 출력이 현재 상태에서만 결정. 대부분 시스템에서 선호
밀리 기계 : 현재 상태와 입력 상태 모두에 의해 결정
유한상태 기계 : 유한 상태, 전이함수들의 집합. 임시 저장장치 없음.
상태 전이함수 : 현재 상태와 입력기호를 보고 그 다음 상태를 나타냄.
DFA : 유한 오토마타
(q, v) : 형상. q-> 현재 상태. v -> 아직 안 읽은 스트링
(q0, w) : 초기 형상
(q, 람다) : 최종 형상(accepting)
(q', 람다) : 최종 형상(rejecting)
NFA : 비결정적 유한 오토마타.
0개 이상의 상태로 move 가능. 선택을 할 수 있다는 의미.
NFA를 먼저 디자인 하고 DFA를 디자인 하라.
백트래킹 : 최적인지 밝혀질 때 까지 계속 검사.
강력하다 : 다른 종류 오토마타에서 수행할 수 없는 일을 수행한다.
람다-클로저 : 람다-트랜지션만을 이용해 도달 가능한 상태들의 집합. s 보함
a-석세서 : 상태s에서 입력기호 a에 의해 도달 가능한 상태들의 집합