Markov Algorithm
Wikipedia : Markov algorithm : À̰ÍÀº ±âÈ£µéÀÇ string ·Î ÀÛµ¿ÇÏ¸ç ¹®¹ý°ú °°Àº ±ÔÄ¢À» »ç¿ëÇÏ´Â string rewriting system ÀÌ´Ù. Markov algorithm Àº °è»ê (Computation) ÀÇ ÀÏ¹Ý ¸ðµ¨ÀÌ µÇ±â¿¡ ÃæºÐÇÑ power ¸¦ °¡Á³°í, µû¶ó¼ Æ©¸µ±â°è (Turing Machine) ¿Í °°Àº °ÍÀ̶ó°í º¼ ¼ö ÀÖ´Ù. ±×°ÍÀº Turing-complete Çϱ⠶§¹®¿¡, Markov algorithm Àº °£´ÜÇÑ Ç¥±â·Î¼ ¾î¶°ÇÑ ¼öÇнĵµ Ç¥ÇöÇÒ ¼ö ÀÖ´Ù.
´ÙÀ½Àº Markov algorithmÀÇ ±âº»ÀûÀÎ µ¿ÀÛÀ» º¸¿©ÁØ´Ù.
Rules
"A" -> "apple"
"B" -> "bag"
"S" -> "shop"
"T" -> "the"
"the shop" -> "my brother"
Symbol string
"I bought a B of As from T S."
¾Ë°í¸®Áò
¾Ë°í¸®Áò ½ÇÇà
¾Ë°í¸®ÁòÀÌ À§¿Í°°Àº ¿¹¿¡ Àû¿ëµÈ´Ù¸é, Symbol string Àº ´ÙÀ½°ú °°Àº ¹æ¹ýÀ¸·Î º¯ÈÇÒ °ÍÀÌ´Ù.
"I bought a B of apples from T S."
"I bought a bag of apples from T S."
"I bought a bag of apples from T shop."
"I bought a bag of apples from the shop."
"I bought a bag of apples from my brother."
¾Ë°í¸®Áò Á¾·á.
Âü°í¹®Çå :
Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191-206.
Markov, A.A. 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.
°è»ê°¡´É¼º ÀÌ·Ð (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Àº Á¾·áÇÑ´Ù