한 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가 임의로 반복되는 형태
