[이산수학]A*와 Regular Expression

한 A 집합이 주어지면 A의 원소들을 이용해서 문자열(String)을 만들 수 있다.

A를 Alphabet 집합이라고 한다면,

A의 알파벳을 이용해 만들 수 있는 모든 문자열의 집합 A*를 만들 수 있다.

이 때 A*는 알파벳을 이용해 만든 'words(단어들)'이 될 것이다.

또한 집합에는 공집합이 있듯이, 아무 글자없는 단어 또한 A*에 포함될 것이다.

이 아무 글자 없는 단어를 'λ'라고 쓰고 'empty string'이라고 부른다.

 

A*에 속하는 w1이라는 단어와 w2라는 단어를 생각해보면

이 둘을 합쳐도 여전히 A*에 속한다는 것을 알 수 있다.

ice + cream = icecream

ice, cream, icecream 모두 알파벳을 가지고 만들 수 있는 단어이므로

A* 원소가 되는데, 이 때 이렇게 단어를 연결하는 것을 Catenation이라고 한다.

Catenation은 접합이라는 뜻이다.

 

그렇다면 이번에는 empty string과의 catenation을 생각해볼 수 있다.

w · λ = w

λ · w = w (empty string은 공백이므로) 가 성립한다.

 

──────────────────────────────────

 

regular expression (정규표현)

 

정규표현은 (,), ∧,∨,* 등등  집합 A에 쓰이는 연산자를 포함해서

문자열을 하나의 기호처럼 만들어내는 것이다.

∧는 and(논리곱), ∨는 or(논리합), *는 앞에서 나온 일종의 반복을 의미한다.

 

예를 들어 A  = {0,1}이라고 할 때,

0*(0∨1)* 를 풀어 써보면

 

(0이 반복) ( (0 또는 1를 포함) 한 것을 반복) 이 된다.

 

a* → aaa, aaaaaa, .....

a(b∨c) → ab, ac

ab(bc)* → ab 다음 bc가 임의로 반복되는 형태