State machines

Contents

컴퓨터 과학에 대한 이해 없이도 프로그램을 개발할 수 있다. 컴퓨터 과학에 대한 기초가 없으면 좋은 프로그램을 만들 수 없다고 하지만 항상 그런건 아니다. 특히 컴퓨팅환경이 고도화되고 추상화 되면서 이러한 경향이 두드러지고 있다. 자동차 운전을 생각해 보면 된다. 자동차는 엄청나게 복잡한 기계지만 고도로 추상화된 덕분에 단지 몇 개의 패달과 변속기, 스티어링 휠에 대해서만 알고 있다면 운전을 할 수 있다. 대부분의 경우 이정도로 충분하지만, 자동차를 전문적으로 다루어야 하는 사람들이 있다. 이 사람들은 기능의 한계까지 밀어 붙여야 하고, 3개의 페달, 변속레벨, 스티어링 휠 이상의 것들을 알아야 한다.

프로그래밍도 마찬가지다. 컴퓨터 과학의 거의 전부를 이해하지 못하더라도 많은 것들을 할 수 있다. PHP나 Python으로 "고객 문의 접수 페이지"를 만드는데 컴퓨터과학이 필요하지 않다. 내가 하고자 하는 일이 무엇인지를 설명할 수 있는 논리적인 사고 방식을 가지고 있으면 충분하다. 이 정도의 논리적 사고는 "상식적이고 합리적인" 수준의 사고를 크게 벗어나지 않는다. 하지만 심각한 계산이 필요한 코드를 작성해야 할 경우에는 컴퓨터가 일하는 방식에 대해서 좀 더 많은 것을 알고 있어야 한다.

이 문서의 목적은 computation에 대한 기본 배경을 설명하는데 있다. 흥미가 있다면 좀 더 높은 수준의 문서를 읽어야 겠지만 지금은 가장 단순한 유한 상태 머신(finite state machine)을 간단히 살펴볼 것이다.

유한상태머신은 알고리즘 디자인을 위해서 사용하는 수학적 도구다. 간단히 설명하자면 상태머신은

1. 일련의 입력을 읽는다.
2. 입력을 읽어서 다른 상태로 전환 한다.
3. 전환할 상태를 지정하는

간단한 일을 한다.

종이를 읽는 장치를 생각해보자. 종이 하나 하나에는 문자 "a" 혹은 "b"가 인쇄되어 있다.

상태 기계가 각 문자를 읽으면 상태가 바뀐(전이한다 라고 한다)다. 아래는 매주 간단한 상태 시스템이다.

원은 기계가 가질 수 있는 상태다. 화살표는 전환을 의미한다. 만약 상태 s 에서 a를 읽었다면 q 상태로 전이될 것이다. a b를 읽는다면 s 상태를 가지게 된다.

위의 종이로 부터 시작한다면, 종이 테이프를 왼쪽에서 오른쪽으로 이동하면서 a를 읽고 q상태로 이동하게 될 것이다. 그리고 b를 읽어서 s상태로 이동, 다음 b를 읽고 s 상태에 그대로 머무를 것이다. 간단하다. 하지만 이것으로 무얼 할 수 있단 말인가 ?

이 과정은 무의미한 것으로 들릴 수 있겠지만, 이런 유형의 접근법으로 (좀 더 쉽게)해결 할 수 있는 많은 문제들이 있다. 예를 들어 HTML 페이지가 아래의 순서로 태그를 포함하고 있는지 확인 하는 것이다. HTML 문서 구조를 추적하는 상태머신은 html 태그를 읽었다고 상태를 변경 할 것이다. 이후 head 태그를 읽으면 head 태그가 끝날 때까지 작업을 수행한다. 성공적으로 최종 상태가 되면 이 문서는 올바른 html 형식을 가지고 있다고 판단할 수 있을 것이다.

이 외에 유한 상태 머신는 주차미터기, 팝 기계, 자동 가스 펌프를 비롯한 모든 종류의 기계장치를 구현하는데 사용 할 수 있다.

지금까지 살펴본 상태머신은 모두 결정론적 상태 기계다. 이것은 예측한 그대로 동작하는 알고리즘을 가지는 상태기계를 의미한다. 모든 상태에서 입력에 대해서는 하나의 전환만 있다. 알고리즘은 초기상태에서 시작해서 종료상태로 끝나며, 사전에 명확하게 정의된 절차에 따라서 종료상태를 향해 전이된다.

비 결정론적 유한 상태 머신는 특정 상태에서 입력이 주어질 경우 하나 이상의 다른 상태로 이어질 수 있는 유한 상태 머신다. 예를 들어 a로 시작하는 문자를 확인하고 다음 문자로 0개 이상의 b 나 c가 나오며, 끝이 c나 d로 끝나는 문자열을 인식 할 수 있는 유한 상태 머신를 만든다고 가정해보자. 이 유한 상태 머신는 아래의 문자열을 검증 할 수 있을 것이다.

• abbbbbbbbbc
• abbbc
• acccd
• accccccd
• ac (b는 0개가 출현)
• ad (c는 0개가 출현)

문자 a 다음에 0개 이상의 b 혹은 c가 나오는 패턴이 될 것이다. 이 상태머신은 아래와 같이 표현 할 수 있을 것이다. 이 상태 머신의 마지막 상태는 문자열이 패턴에 일치하는지에 대한 true, false일 것이다.

이 상태머신의 문제가 보이는가 ? 이 상태 머신은 출발지점에서 어느 패스를 선택해야 할지 알 수 없다. 문자 a를 읽으면 q 혹은 r 둘 중 하나의 경로를 가지게 될 것이다. 이 문제를 해결 할 수 있는 가장 간단한 방법은 가능한 모든 경로를 확인 하면서, 뒤로 빠져나가거나 해당 경로를 선택하는 것이다.

이 방식은 체스 소프트웨어가 사용하는 방식이다. 체스 소프트웨어는 모든 가능성을 확인해서 가장 많은 이점을 줄 수 있는 경로를 선택한다.

다른 옵션은 비결정론적 기계를 결정론적 기계로 변환하는 것이다. 비결정론적 기계의 흥미로운 점은, 결정론적 기계로 전환할 수 있는 알고리즘이 있다는 것이다. 하지만 비결정론적 기계에 비해서 훨씬 복잡하다는 문제가 있다. 다행이 위의 예제는 비교적 단순한 방식으로 변환 할 수 있다. 아래는 비결정론적 기계를 결정론적 기계로 변환한 모습이다. 아래의 결정론적 기계는 모든 문자열에 대해서 t 또는 v의 최종상태에 도달한다.

비결정론적 모델은 4개의 상태와 6개의 전환이 있다. 결정론적 모델은 6개의 상태, 10개의 전환과 2개의 가능한 최종상태가 있다. 복잡도는 보통 기하급수적으로 증가한다. 비결정론적 기계는 매우 거대한 결정론적 기계를 만들 수 있다.

위의 문자열을 이용한 상태 기계를 보면 정규 표현식과 유사한 점을 찾을 수 있을 것이다. 실제 정규표현식와 유한 상태 머신는 비슷한 제한을 가지고 있다. 둘다 유한 메모리(finite memory)를 이용해서 패턴을 일치시키는 작업을 할 수 있다. 위의 문자열 예제를 정규표현 식으로 표현해보자. 이 정규표현식은

• a로 시작하며 그 다음에 N개 이상의 b 가 출현하고 c로 끝나는 패턴 혹은
• a로 시작하며 그 다음에 N개 이상의 c 가 출현하고 d로 끝내는 패턴에 일치한다.

위의 정규표현식은 유한 메모리로 처리 할 수 있다. 하지만 N 개의 a에 대해서 동일한 N개의 b가 출현하는 문자열을 일치해야 하는 경우는 어떨까 ? 이 패턴을 일치하는 문자열은 아래와 같을 것이다.

• ab
• aabb
• aaaaaabbbbbb
• aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

유한상태기계로 쉽게 풀 수 있는 문제인 것 같다. 하지만 상태를 벗어나기 위해서는 무한한 수의 상태를 거정해야 하는데, 이 상태는 더 이상 유한상태기계가 아닌 것이 된다. 20개의 a 다음에 20개의 b가 오는 패턴을 검사하는 것은 문제 없다. 하지만 문자열이 매우 길어질 경우 코드를 다시 만들어야 한다. 문자열이 매우 길 경우 메모리 부족으로 컴퓨터가 인식하는데 실패 할 수 있기 때문이다.

이것은 Pumping Lemma로 알려져 있다. 기본적으로 패턴이 위 예제와 같이 반복될 수 있는 구간이 있는 경우 패턴은 규칙적이지 않다. 즉 정규표현식이나 유한상태 머신은 패턴과 일치하는 모든 문자열을 인식 할 수 없다.

예제를 살펴보면 이 유형은 Open 태그가 Close 태그의 쌍을 가지는 HTML과 유사함을 알 수 있다. 따라서 정규표현식이나 유한 상태 머신를 이용해서 HTML 페이지가 올바른 순서로 html, head 및 body 요소를 가지고 있는지 인식 할 수는 있지만, 정규표현식으로 전체 HTML 페이지가 올바른지 그렇지않은 지는 인식 할 수 없다. 왜냐하면 HTML은 정규패턴이 아니기 때문이다.

그렇다면 비 정규패턴은 어떻게 인식 할 수 있을가 ? 튜링 머신라고 하는 상태 기계와 유사한 이론적 장치를 이용해서 인식 할 수 있다. 튜링 머신는 유한상태 기계와 유사하지만 데이터를 지우고 쓸 수 있다는 차이가 있다.

튜링 기계는 앨런 튜링이 1936년 제시한 개념이다. 앨런 튜링은 1948년 그의 에세이 "Intelligent Machinery"에서 그의 기계가 아래와 같이 작동한다고 설명했다.

...무한한 저장공간은 무한한 길이의 테이프로 나타낼 수 있다. 이 테이프는 하나의 기호를 인쇄할 수 있는 정사각형 셸로 쪼개져 있다. 기계속에는 하나의 기호가 있는데 이를 "읽힌 기호"라고 한다. 이 기계는 "읽힌 기호"를 변환할 수 있는데, 이 기계의 행동은 오직 읽힌 기호만이 결정 할 수 있다. 테이프는 앞뒤로 움직일 수 있어서 모든 기호들은 적어도 한번은 기계가 읽을 것이다.

컴퓨터는 무한한양의 메모리를 가지고 있지 않지만, 튜링 기계를 이용하면 유한한 메모리로 문제를 처리 할 수 있다. 튜링 머신은 컴퓨터 프로세스가 어떻게 작동하는지를 시각적으로 이해할 수 있는 가상의 기계장치를 제공한. 특히 튜링 기계는 계산의 한계를 이해하는데 많은 도움을 준다. 언젠가 시간이 되면 튜링 머신을 정리해봐야 겠다.

요점이 무엇일까 ? 이게 도대체 PHP 폼을 만드는 것과 같은 일에 어떤 도움을 줄 수 있다는 얘긴가 ? 상태 기계는 컴퓨팅의 핵심 개념이다. 특히 비 결정적 상태 머신을 디자인 할 수 있다는 것과 동일한 일을 하는 결정론적 상태 머신이 존재한다는 인식을 가지는 것은 그렇지 않은 것과 비교해서 문제를 바라보는데 중요한 이점을 제공한다. 가장 큰 이점은 문제 해결을 위한 알고리즘을 설계하는데 있어서, 유용한 생각의 틀을 제공한다는 점이다. 일단 당신이 적당한 알고리즘을 가지고 있다면 그 알고리즘을 효윺적인 형태로 변환할 수 있다.

유한 상태 머신와 정규 표현식이 기능적으로 같다는 것을 이해하면 정규 표현식 엔진에 대한 흥미로운 아이디어를 가질 수 있으며, 특히 컴파일하자 않고 변경할 수 있는 유연한 비지니스 룰을 만들 때 유용하게 사용 할 수 있다.

컴퓨터 과학의 토대는 문제 "X"가 주어졌을 때, X를 왜 풀 수 없는지 그리고 그 이유가 무엇인지를 알 수 있는데 있다. 문제를 풀 수 없다는게 왜 중요하냐고 생각 할 수 있겠지만, 여기서 부터 시작 할 수 있다.

1. 나는 문제 X를 풀 수 있는 방법을 모른다.
2. 하지만 Y 문제를 풀 수 있는 방법을 알 고 있다.
3. 그리고 Y 문제를 풀었던 그 방법을 X 문제를 풀도록 변환 할 수 있다.
4. 그러므로 나는 X 문제를 풀 수 있다.

• State machines computer science