[Automata Theory] Language
언어(Language)라는 개념은 우리에게도 굉장히 친숙한 개념이다. 늘 사용하는 것이 언어이고 이 글도 언어의 한 종류인 한국어와 영어로 쓰여진 무언가 이다. 그렇다면 언어의 정의는 무엇일까? 우선, 언어를 정의하기 위해서는 '알파벳'과 '스트링'이라는 것이 필요하기에 이들을 먼저 알아보자. 1. 알파벳 $\Sigma$는 문자들의 Finite Set이다. 예를 들어, 영어의 경우 $\Sigma=\{a, b,\cdots,z\}$이고, 이진수의 경우 $\Sigma=\{0,1\}$이다. 2. 스트링은 알파벳 $\Sigma$에 속해있는 문자들의 유한한 나열이다. 예를 들어, "abcd"는 $\Sigma=\{a, b,\cdots,z\}$상의 스트링이다. 3. $\Sigma$상의 모든 스트링의 집합은 $\Sigm..
Regex Quantifier 사용시 주의할 점
보통 문자열이나 HTML 코드 등을 파싱 할 때 Regex(Regular Expression, 정규표현식)를 많이 사용한다. Regex를 이용하면 모든 문자열을 효율적으로 표현할 수 있기에 잘 다루면 큰 도움이 된다. 이런 Regex에는 Quantifier라는 수를 표현할 수 있는 문법이 있는데, 주로 다음을 일컫는다. ? : 0번 또는 1번 * : 0번 이상 + : 1번 이상 {N,} : N번 이상 {N,M} : N번 이상 M번 이하 예를 들어, a+은 a가 1번 이상 반복되는 'a', 'aa', 'aaa' 등을 말한다. 이때 주의해야 할 Quantifier는 제일 마지막에 있는 {N,M}이다. 바로 띄어쓰기를 조심해야 하는데, {N, M}과 {N,M}은 엄연히 다른 것으로 후자가 Quantifier의..
