이번엔 DFA에서 State를 줄여나가는 방법이다. 먼저 state를 2개로 만든 모양이다. 빨간색 부분을 1구역, 파란색 부분을 2구역 이라고 보자. 1구역에는 A, B, D가 있고 2구역에는 C,E가 있다. ABD는 각각 a 일때 1구역에 머물러있고, b 일때는 A는 1로, 나머지는 2구역으로 이동한다. 표로 정리하면 이렇게 된다. a일 경우와 b가 같아야 한 state로 묶을 수 있으며, 현재 ABD state는 B,D경우가 다르므로 하나의 state로 만들 수 없다. 그러면 좀 더 쪼개서 3개의 state로 만들어보자. 구역을 3개로 나누어 보았다. 이렇게 되면 각 구역에서 선택지에 따라 일정한 곳으로 이동하게 된다. 이러한 식으로 정리가 가능하다. 그럼 각각 1, 2, 3을 다시 오토마타로 만들..

오토마타 경우의 수중에 ε는 아무 조건 없이 갈 수 있는 경우를 말한다. 이 경우를 묶어서 ε-closure라고 부른다. ε - NFA 예시 1에서 epsilon을 통하여 무조건 갈 수 있는 경우를 e-closure(1)이라고 표현합니다. closure(1)일때 a가 주어지면 2로 가게되고 2에서는 epsilon으로 갈 수 있는 곳이 없기 때문에 자기 자신 closure(2)가 됩니다. c가 주어진다면 3으로 이동하게 되고 3에서는 epsilon으로 4로 이동할 수 있기 때문에 closure(3)이 되고 자기 자신과 4를 포함한 [3,4]가 됩니다. 이 방법은 DFA로 변환할 때 2의 n승 만큼 터미널을 만드는게 아니라 e-closure를 통해 epsilon으로 갈 수 있는 터미널들을 정의하고 직접 가보..

어휘를 분석하여 토큰을 추출하려면 형식 언어와 정규 언어에 대한 이해가 필요하다. 이번엔 정규 표현에 대해 알아보도록 하자. 개념 정규 표현 상에서는 + 기호가 or 을 나타낸다. (0 + 1)* 일 경우 0또는 1로 이루어질 수 있는 모든 집합을 말한다. (aa)*(bb)*b 와 같은 정규 표현이 있다. 위 정규표현은 이와 같은 수학 식으로도 정의할 수 있다. aa 로 이루어질 수 있는 집합이므로 2n개 만큼이 나오고, bb 로 이루어질 수 있는 집합에 마지막 b가 있어야 하므로 2m+1 개가 나와야 한다. n, m 둘다 입실론(공백)이 될 수도 있으므로 0 보다 크거나 같다고 명시해주어야 한다. 정규 표현의 방정식 저번에 배웠던 Formal Language를 여러 형태로 만들어 보자 그중 새로 배울 ..

컴퓨터가 말하는 언어로, 정확하게 표현하기 위해 문법을 알아야 한다. 형식 언어를 이해하고 형식 문법을 이해해야 추후에 어휘를 분석할 수 있다. 기본 용어 정의 - Alphabet Formal Language에서의 Alphabet은 언어의 문장을 이루는 기본 심볼이다. 정의 - String 알파벳 집합에 대한 기호들을 나열한 유한 수열으로, {a,b,c} 일때 ccba는 string 이다. 문자열 연산 Length of String 심볼의 갯수를 세는 것으로, {a,b,c} 집합에서의 aba의 length는 3이고, {do, case, while} 집합에서의 docase 는 length가 2이다. Concatenation of String 두개 이상의 문자열을 연결하여 문자열을 만드는 것으로, u = a..