1장 Introduction to the Theroy of Computation

1. 이번 장에서 다루는 내용

1.1 오토마타 관련 기본 수학

 - 집합이론

 - 트리와 그래프

 - 기본적인 증명법들(귀납법, 연역적 추론법, 반례)

1.2 Language, Grammar, Automata 개념

2. 집합(Set)

집합이란? 

- 서로다른 대상들이 모여 이루는 새로운 대상.(https://ko.wikipedia.org/wiki/%EC%A7%91%ED%95%A9)

집합 관련 기호

- 포함관계(Membership)

집합 표현 예제

집합의 Powerset

Powerset 2^S는 집합 S의 모든 subset의 집합이다.

집합 S = {a,b,c}에 대하여 집합 S의 Powerset 2^S = { {}(공집합), {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }

드모르간의 법칙

Function

: 집합을 입력으로 받고 하나의 숫자를 출력으로 내는 함수.

Relation

: S X S의 임의의 서브클래스

3. 그래프

그래프는 2개의 유한 집합 Vertices, Edges로 구성됩니다.

4. 트리

트리는 그래프의 일종으로, Cycle이 없는 Directed Graph입니다.

5. 증명법

- 연역적 추론(모든 인간은 죽는다. 소크라테스는 인간이다. 따라서 소크라테스는 죽는다.)

- 귀납법(소크라테스는 아테네인이다. 소크라테스는 철학자이다. 그러므로 모든 아테네인들은 철학자다.)

- 반례제시(소크라테스는 죽지 않는다. 따라서 모든 인간이 죽는것은 아니다.)

6. Language

6.1 용어 정리

- Alphabet 

Symbol(a,b,c,...)들로 구성된 유한한, 비어있지 않은 집합 ∑

- String

유한한 갯수의 Symbol들이 연속으로 이어진 것

- Concatenation

두 개의 스트링을 잇는다.

- Reverse

뒤집기

- Length

스트링의 길이

- Empty String  λ

비어있는 문자열을 나타내는 람다문자

- Substring, Prefix & Suffix

- Repeats

반복

- Infinite Alphabets

: ∑의 Symbol을 0개 이상 Concatenate해서 얻은 모든 String의 집합(Star-Closure)

(Positive Closure)

ex1)

라고 하면

이다.

ex2) 

집합 

의 Language이고,

Finite Language이다.

ex3)

집합 은

의 Language이고,

Infinite Language다.

- Language의 일반적인 정의

Language L은 일반적으로  의 Subset으로 정의된다.

7. Grammars

7.1 Grammar란?

- Language를 표현하기 위한 메커니즘

Grammar G는 다음의 quadruple로 표현된다.

• G=(V,T,S,P).

• V : 변수, 유한한 객체의 집합.

• T : Terminal Symbol. 유한한 객체의 집합.

• S V: Start Variable. 특별한 Symbol

• P: Productions. 유한한 객체의 집합

• V와 T는 비어있지 않고, disjoint하다.

7.2 Production Rule 이란?

- Grammar가 String을 어떻게 변화시키는지를 나타내는 것.

- Grammar = Language + Production Rules

ex) Grammar G=({S}, {a,b}, S, P)이고, Production Rule P가

• S -> aSb

• S -> λ

라고 하면,

• S => aSb => aaSbb => aabb

7.3 Derivation

• x -> y

• w = uxv

• z = uyv

라고 하면

w => z 이다.(z is derived from w)

 : w1=>w2=>...=>wn (wn이 w1으로부터 derive 될 수 있다.)

7.4 Language

Grammar G=(V,T,S,P)에 의해 생성되는 Language는

이다.

ex) Grammar G=({S}, {a,b}, S, P)이고, Production Rule P가

• S -> aSb

• S -> λ

라고 하면,

G의 Language 는 다음과 같다.