1. regular expression

연결 concatenation
s1 = ab, s2 = aaa 이면 s1s2 = abaaa

 

알파벳(alphabet)Σ - 심볼들의 유한집합
알파벳 Σ상에서의 스트링(string) s - Σ에서 가져온 심볼을 유한개 연결한것(concatenate)
Σ* - 어떤 알바벳 Σ에서 생성 가능한 모든 스트링의 집합
알파벳 Σ상에서의 언어(language) L - Σ*의 부분집합(subset)

 

union (합 집합)
intersection(교 집합)
complementation(보 집합)
difference(차 집합)

 

스트링들을 lexicographic order(주: alphabetic order와는다름)로 나열한다는 말은 스트링의 길이(length) 순서를 지키면서 alphabetic 순서로 나열하는 것임.

Σ={a, b}일 때 다음은 lexicographic 순서임

길이가 0인 스트링 : e,
길이가 1인 스트링 : a, b,
길이가 2인 스트링 : aa, ab, ba, bb,
길이가 3인 스트링 : aaa, aab, aba, abb, baa, bab, bba, bbb