String and Languages
string은 character를 모아둔 것을 의미한다.(문자열은 문자를 모아둔 것을 의미한다...)
-
우리는 먼저 alphabet을 정의해야하는데, alphabet은 symbol들을 모아둔 것을 alphabet이라고 한다. 여기서 character라고 하지 않고 symbol이라고 한 이유는 a~z뿐만 아니라 여러 기호를 사용하기 때문에 symbol이라고 명명한다.
영어에 대한 알파벳은 {a~z}라고 할 수 있겠지만, 이진수의 세계에서는 {0,1}일 것이다. 또한 섞어서 쓰는 것도 가능하다. 이렇기에 symbol이라고 부르는 것이다. -
String over an alphabet : alphabet에서 symbol들을 뽑아서 만든 유한한 sequence를 말한다. Σ1 = {0,1}에서는 01001이 가능할 것이고, Σ2 = {a, b, c, . . . , z}에선 abracadabra도 가능할 것이다.
-
w는 string over an alphabet의 길이를 의미하며, |w|라고 쓴다.
-
|w| == 0 인 string을 empty string이라고 부르며, ε(입실론)으로 쓴다. 비어있다는 것을 표시하기 위해서 사용한다.
-
|w| == n이면, w = w1w2 · · · wn 이렇게 쓸 수 있으며, wi ∈ Σ라는 조건을 가진다.
-
w를 반대로 쓰면 w^R로 표시하며(w^R = wnwn-1 · · · w1 ), 원래와 반대로 나열된다.
-
Substring은 w 안에서 연속으로 요소들을 가지는 string을 말한다. abcd라는 string 이 있을때 abc같은 것들.
-
string x의 길이가 m이고, string y의 길이가 n일때, x와 y의 concatenation(결합)은 xy로 표기하며, x가 끝나면 y가 시작되는 string을 말한다.
-
Lexicographic ordering은 string의 사전 순서를 의미한다. 잘 구성된 사전 순서를 shortlex order 또는 string order라고 부른다.
lauguage는 string들을 모아둔 것이다.
