computation theory (5) - context-free grammar and pushdown automata

    context-free grammar(CFG)는 DFA나 RE보다 더 강력한 descriptive power를 가진 모델이다. CFG는 4-tuple로 정의한다.

context-free grammar 

V : variables의 집합

: terminals의 집합

 R : rules의 집합

 S : 인 start variable

CFG로 들어지는 language를 context-free language라고 한다. Chomsky normal form은 CFG의 간단하고 유용한 form으로 모든 rule이  의 형태를 가진 CFG이다. 모든 CFG는 CNF으로 변환가능하다.

Pushdown atomata(PDA)는 stack을 가진 finite automata이다. PDA는 CFG와 descriptive power면에서 동일하며 6-tuple로 정의된다.

pushdown automata 

pushdown automata와 context-free grammar의 equivalence에 대한 증명은 추후 포스팅하겠습니다.