Context-Free Grammer

<aside> 💡 all Productions in P are $A→x$

s.t $A \in V and x \in (V \cup T ) ^*$ 즉 lhs는 single variable 하나만 와야 하고(context free: 주변이없음), rhs는 상관 없다

</aside>

*all RL is CFL

Derivation

A Sequence of the productions of a CFG to infer that a certain string is in the language

• Use Productions from HEAD to BODY

  • Leftmost, Rightmost derivation: 가장 왼쪽/오른쪽의 변수를 바꿈

  

• Recursive Inference Use productions from BODY to HEAD 위 과정의 반대.

• Start State에서 시작할 필요는 없다!

Iterative Derivation

double arrow: one-step derivation

위에 star: multi-step derivation (여러번 한거를 그냥 표기한거)

• Sentential Form
  • Start에서 출발해서 derivation을 통해 얻어진 결과물: Sentential Form $S \overset {*}{\Rightarrow} \alpha$

Context-Free Language

L is context free language ↔ there is context-free G s.t. L = L(G)

$L(G) = \{ w \in T^* | S \overset {*}{\Rightarrow} w \}$

: start state에서 시작한 모든 w의 집합