Formal Language & Grammar

Language

Alphabet : 최종 상태 심볼들의 집합이다! ex) {A,B,C,...,z} , {do,switch,...,if}

String : Alphabet 들의 집합이다. 만약 알파벳 T가 {a,b}라면 a,b,aa,ab,bba 등이 String이 된다.

* w = bba의 length(|w|)는 3이다!

epsilon ( ε ) : empty string 즉, 길이가 0인 스트링이다!

: T라는 알파벳으로 생성할 수 있는 모든 스트링이다 {ε,a,b,aa,ab, ... }

: 에서 입실론을 제외한 값이다!

Language :  중 필요한 것만 모은 부분집합이다! (특정 규칙?)

* Language끼리는 곱셈이 가능하다! {a,b} {1,2}라면 {a,1,a2,b1,b2}가 가능하다!

Power : Language를 처럼 지수승을 가지게끔 표현할 수 있다.

* 은 ε이 아니라 {ε} 이다! ε이라는 원소를 가지는 집합이다!!!

Grammar

G = (,,P,S) 로 정의한다.

 : nonterminal symbols로 끝나지 않고 계속 상태 전이를 할 수 있는 심볼들이다.

 : 더 이상 전개가 되지 않고 종료가 되는 심볼이다.

P : Production Rule로 에서 알파를 베타로 변형시키는 형식을 가진 액션을 뜻한다.

S : Start symbol로 상태 전개가 진행되는 시작점이다.