Markov Algorithm

 

Andrei Markop

Wikipedia : Markov algorithm : 이것은 기호들의 string 로 작동하며 문법과 같은 규칙을 사용하는 string rewriting system 이다. Markov algorithm 은 계산 (Computation) 의 일반 모델이 되기에 충분한 power 를 가졌고, 따라서 튜링기계 (Turing Machine) 와 같은 것이라고 볼 수 있다. 그것은 Turing-complete 하기 때문에, Markov algorithm 은 간단한 표기로서 어떠한 수학식도 표현할 수 있다.

다음은 Markov algorithm의 기본적인 동작을 보여준다.

Rules

Symbol string

"I bought a B of As from T S."

알고리즘

  1. 화살표의 왼쪽에 있는 string 들중의 어떤 것이 symbol string에서 찾을 수 있는지를 보기위해 위에서 아래로 rule 들을 체크한다.
  2. 만일 아무것도 발견되지 않으면 실행을 중단한다.
  3. 만일 한 개 이상 발견되면, symbol string에서 가장 왼쪽에 있는 matching text를, 해당하는 rule에서 찾아서 화살표의 오른쪽에 있는 text 로 바꾼다.
  4. 1 단계로 돌아가서 계속 수행한다.

알고리즘 실행

알고리즘이 위와같은 예에 적용된다면, Symbol string 은 다음과 같은 방법으로 변화할 것이다.

알고리즘 종료.

참고문헌 :

계산가능성 이론 (Computability Theory)   계산 (Computation)   계산복잡도이론 (Computational Complexity Theory)

 

Post production system 이후의 production rule 에서의 발전이 Markov 에 의해 이루어 졌다. 즉 control mechanism을 만든 것이다. input string 의 우선순위 순서대로 rule 을 순서지워 가장 우선순위가 높은 rule 을 적용할수 없으면 다음 rule을 수행한다. Markov algorithm은 last production 이 string 에 적용할수 없든가, period마크가 나타나면 종료한다.또한 substring 에도 적용할수 있다.

1. AB -> HIJ                                        

 위의 rule에서 input string GABKAB 는 GHIJKAB를 낳고 최종적으로 GHIJKHIJ 가 된다

2.  A -> ^   

null string을 의미하는 ^에 의해 string에서 문자 A를 지운다.

3. AxB -> BxA

소문자 a, b, c,..로표현되는 특수 심볼은  single character variable 로서 현대 expert system 언어에서 중요한 부분이다. 소문자 x 는 문자 A 와 B를 바꾼다.

4. 그리스 문자 α,β,γ..등등은 string 의 특수한 punctuation (구두점, mark point) 목적으로 사용된다.

example)

다음은 input string 의 첫문자를 끝으로 이동시키는  Markov algorithm 이다. 3개의 rule이 주어지며 입력순서대로 우선순위가 부여되어 수행된다.

          1. αxy -> yαx

          2. α -> ^.      :   null 문자와 종료 period가 있다

          3.  ^ -> α

input string ABC에 대한 Markov algorithm 의 수행
 

Rule

Success or Failure

String

1

F

ABC

2

F

ABC

3

S

αABC

1

S

BαAC

1

S

BCαA

1

F

BCαA

2

S

BCA

여기서 α 는 기존 program 언어의 임시변수와 같은 역할을 한다. 그러나 값을 가지는 대신에 input string 의 변화를 야기하는 place holder 역할을 한다. 작업이 수행되면 2번 rule에서 α 는 제거되고 program은 종료한다