[Automata][WIP] Language, Grammars, Automaton

이번 포스팅에서는 Chapter 1의 내용을 다뤄보려고 한다! Chapter 1 답게 기본 상식들이 많이 나와서 이미 아는 부분들은 생략 했다. Introduction to the Theory of Computation에서는 증명 방법 - induction(귀납법), contradiction(귀류법) 내용이 간단하게 나오지만 Language, Grammar, Automaton이 이 단원의 포인트라서 이 부분만 집중적으로 다뤄보려고 한다. 

Languages

string의 집합! string = {a, b, c, ...} 라면 string으로 만든 aa, bb, ccc, 등의 문자열이 language이다. 

• Reverse: 거꾸로 string= {a, b}라면 {a, b, aa, bb, ab, ...} 등 0개 이상의 symbol을 접합해서 만들 수 있는 language.
• Concatenation: 두개의 문자열 접합
• Star-closure(Σ*):  string= {a, b}라면 {람다, a, b, aa, bb, ab, ...} 등 0개 이상의 symbol을 접합해서 만들 수 있는 language.
• Positive-closure(Σ+): string= {a, b}라면 {a, b, aa, bb, ab, ...} 등 0개 이상의 symbol을 접합해서 만들 수 있는 language.

Grammars

Language와 Grammar를 구분할 수 있어야 한다. 헷깔려...

 

Grammar G는 quadrople G = (V, T, S, P) 로 정의되는데 

 

V: variable의 유한집합

T: terminal symbol의 유한집합

S: start하는 variable, T에 항상 포함되어있어야 한다

P: production의 유한 집합

 

V랑 T는 항상 원소가 1개 이상이어야 하고, 교집합이 없어야 한다.

 

예시) G = ({S}, {a,b}, S, P)이고 P는 S->aSb, S->ƛ이다. 

 

Automaton

• Deterministic Automata: 현재 상태에 의해서 move가 결정된다. 
• Nondeterministic Automata: 여러개의 move가 있을 수 있다. 
• Accepter(인식기)
• Transducer(변환기)