[Automata][WIP] 정규 언어와 정규 문법

이번에는 chapter 3의 내용을 다루려고 한다!.!

정규 표현식 ( Regular Expression ) 

정규표현식은 알파벳, 덧셈(+), 곱셈(·), 제곱(*)으로만 이루어져 있다. 

덧셈

a+b는 a랑 b로 이루어진 집합에서 뽑아서 쓰는 것이다.  a+b = {a, b} 라고 생각하자. 

제곱

(a+b)*는  ƛ, a, b, aa, ab, ba, bb, aaa ,,, 등이다. 순서 상관 없다!

a*는 0개 이상 반복이다. 

 

예1 ) r = (a+b)*(a+bb)

예2) r = (aa)*(bb)*b

 

정규 표현식과 정규 언어의 관계 

 

정규 문법 ( Regular Grammar )

 

예1)

V_0 -> aV_1

V_1 -> abV_0 | b

V_0이 시작임