Post  Systems

 

Wikipedia : Post correspondence problem

Production system Àº Emil Post °¡ óÀ½ symbolic logic ¿¡ »ç¿ëÇÏ¿´´Ù. ±×´Â ¾î¶² ½Ã½ºÅÛÀÇ ¼öÇаú ³í¸®µµ production rule systemÀ¸·Î ¼­¼úµÇ¾î ³î¶ó¿î °á°ú¸¦ º¸Àδٴ °ÍÀ» Áõ¸íÇÏ¿´´Ù. ±×°ÍÀº major classes of knowledge¸¦ Ç¥ÇöÇϴµ¥ Å©°Ô À¯¿ëÇÏ´Ù. rewrite rules ¶ó´Â ¿ë¾îó·³ ¾ð¾îÀÇ ¹®¹ý (grammar of a language) À» Á¤ÀÇÇϴµ¥ ¶ÇÇÑ À¯¿ëÇÏ´Ù. ÄÄÇ»ÅÍ ¾ð¾î´Â ´ë°³ production rules ÀÇ BNF (Backus-Naur Form)À» »ç¿ëÇؼ­ Á¤ÀǵȴÙ.

¾î¶°ÇÑ ¼öÇÐÀû, ³í¸®Àû ½Ã½ºÅÛµµ rule ÀÇ ÁýÇÕÀÌ´Ù. ¿©±â¼­ rule Àº ÇϳªÀÇ string of symbol ÀÌ ¶Ç´Ù¸¥ symbol ·Î ¾î¶»°Ô º¯È¯ÇÏ´ÂÁö¸¦ ±ÔÁ¤ÇÏ´Â °ÍÀÌ´Ù. ÁÖ¾îÁø input stringÀ» antecedent ¶ó ÇÏ°í production rule ¿¡ ÀÇÇØ »õ·Î ¸¸µé¾îÁø stringÀ» consequent ¶ó ÇÑ´Ù. ÀÌ°ÍÀº expert system ¿¡¼­ÀÇ input data(string) ¿Í transformation µÈ output string ·Î¼­ ÀÌ¿ëµÇ¾îÁø´Ù.

¿©±â¼­ string ÀÇ Á¶ÀÛÀº syntax ¿¡ µû¸¥ °ÍÀÌÁö ¾î¶² semantic ( fever, aspirin, patient ÀÇ ÀÇ¹Ì ) ¿¡ µû¸¥ °ÍÀÌ ¾Æ´Ï´Ù. Àΰ£Àº string ÀÇ ½Ç¼¼°è¿¡¼­ÀÇ Àǹ̸¦ ¾ËÁö¸¸ Post production systemÀº ´ÜÁö ÇϳªÀÇ stringÀ» ´Ù¸¥ string À¸·Î º¯È¯½ÃÅ°´Â ¹æ¹ýÀÏ »ÓÀÌ´Ù.

Antecedent -> Consequent

person has fever -> take aspirin

È­»ìÇ¥´Â ÇϳªÀÇ string ÀÌ ´Ù¸¥ °ÍÀ¸·Î º¯È¯ÇÏ´Â °ÍÀ» ÀǹÌÇÑ´Ù. ÀÌ·¯ÇÑ ruleÀ» º¸´Ù ´õ Ä£¼÷ÇÑ IF THEN Çü½ÄÀ¸·Î Çؼ®ÇÒ¼ö ÀÖ´Ù

IF person has fever THEN take aspirin.

multiple antecedents ÀÇ °æ¿ì¿¡´Â ´ÙÀ½Ã³·³ ¾´´Ù. ¾Æ·¡ ¹®ÀåÀÇ AND ´Â string ÀÌ ¾Æ´Ï°í connective À̸ç rule ÀÌ ¿©·¯°³ÀÇ Á¶°ÇÀ» °¡Áø´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù.

person has fever AND fever is greater than 102 -> see doctor

Post production system Àº production rule ÀÇ ÁýÇÕÀ¸·Î ±¸¼ºµÈ´Ù

1. À§ÀÇ 4°³ÀÇ rule Áß¿¡¼­ Çϳª¸¸ ¼öÇàµÉ¼öµµ ÀÖ°í ÀüºÎ¼öÇàµÉ¼öµµ ÀÖ°í Çϳªµµ ¼öÇàµÇÁö ¾ÊÀ»¼öµµ ÀÖ´Ù.

2. 4°³ÀÇ rule ÀÇ ¼ø¼­°¡ ¹Ù²ï´Ù°í ÇÏ¿©µµ ¾Æ¹«·± ¹®Á¦°¡ ¹ß»ýÇÏÁö ¾Ê´Â´Ù.

3. óÀ½ µÎ °³ÀÇ rule¿¡¼­ °°Àº string (car won't start) ÀÇ °æ¿ì¿¡ ¾î¶² ruleÀ» ¸ÕÀú ¼öÇàÇϴ°¡?  Áï control mechanism ÀÌ ¾ø´Ù.  Post production system ÀÌ expert systemÀÇ ±âÃʸ¦ ÀÌ·ç¾úÁö¸¸ ½ÇÁ¦ program¿¡ Àû´çÇÏÁö ¸øÇÑÀÌÀ¯´Â rule ÀÇ Àû¿ëÀ» guide ÇÏ´Â control strategy °¡ ¾ø±â ¶§¹®ÀÌ´Ù. ÀÌ°ÍÀº Å« µµ¼­°ü¿¡¼­ index ¾øÀÌ Ã¥À» ã´Â °Í°ú °°À¸¸ç ,¾î·Æ°Ô ã¾Ò´Ù°í ÇÏ¿©µµ ´Ù¸¥ Á¾·ùÀÇ Ã¥À» ãÀ¸·Á¸é ¶È°°Àº °úÁ¤À» ¹Ýº¹ÇÏ´Â °Í°ú °°´Ù.

term :

term :

Æ÷½ºÆ®½Ã½ºÅÛ (Post System)    Æ©¸µ ±â°è (Turing Machine)   °è»ê (Computation)   °è»ê°¡´É¼º ÀÌ·Ð (Computability Theory)   »ý¼º±ÔÄ¢ (Production Rule)    Àü¹®°¡½Ã½ºÅÛ (Expert System)   Áö½ÄÇ¥Çö (Knowledge Representation)    Emil Post