Chomsky hierarchy

Chomsky hierarchy

1번 유형을 CSL(context-sensitive language), 2번 유형을 CFL(context-free language) 마지막으로 3번 유형을 RL(regular language)

화살표 오른쪽에 nonterminal이 없는게 존재

화살표에 왼쪽에 nonterminal만 들어가야 하는데 terminal이 들어감

조건을 모두 만족 RL 중에서도 Right Linear이다

 

---

Regualr expression

Regular expression은 union,star,concatenation 모두 가능하다.

regular expression을 할 때 주의 할 점은 concatenation은 교환법칙이 성립하지 않는다는 것이다.

---

Syntax chart

---

BNF(Backus-Naur Form)

 

---

EBNF(Extended BNF)