°è»ê ÀÌ·Ð °³¿ä

 

Çü½Ä ¾ð¾î¿Í ¿ÀÅ丶Ÿ : Peter Linz Àú¼­, ÀåÁ÷Çö. ±èÀÀ¸ð. ¾ö¿µÀÍ. Çѱ¤·Ï °ø¿ª, »çÀÌÅع̵ð¾î, 2001 (¿ø¼­ : An Introduction to Formal Languages and Automata. 3rd ed, Jones and Bartlett. 2001), Page 1 ~ 37

 

1. ¼öÇÐÀû °³¿ä ¹× Ç¥±â¹ý

     (1) ÁýÇÕ

     (2) ÇÔ¼ö¿Í °ü°è

     (3) ±×·¡ÇÁ¿Í Æ®¸®

     (4) Áõ¸í ±â¹ý

     ¿¬½À¹®Á¦

2. ¼¼ °¡Áö ±âÃÊ °³³ä

     (1) ¾ð¾î

     (2) ¹®¹ý

     (3) ¿ÀÅ丶Ÿ

     ¿¬½À¹®Á¦

3. ÀÀ¿ë

     ¿¬½À¹®Á¦

 

ÄÄÇ»ÅÍ °úÇÐÀº ¸Å¿ì Çö½ÇÀûÀÎ Çй®ÀÌ´Ù. À̸¦ °øºÎÇÏ´Â »ç¶÷µéÀº ÀÌ·ÐÀûÀÎ °íÂûÀ» ÇÊ¿ä·Î ÇÏ´Â ¹®Á¦º¸´Ù´Â Çö½ÇÀûÀÌ°í ½ÇÁ¦·Î À¯¿ëÇÑ ¹®Á¦µéÀ» ÇöÀúÇÏ°Ô ÁÁ¾ÆÇÏ´Â °æÇâÀ» °¡Áø´Ù. ƯÈ÷, ÀÌ·¯ÇÑ °æÇâÀº ½Ç¼¼°è¿¡¼­ ÇÊ¿ä·Î ÇÏ´Â º¹ÀâÇÏ°í ¾î·Á¿î ÀÀ¿ë ºÐ¾ß¸¦ ´Ù·ç´Â ÄÄÇ»ÅÍ °úÇеµµé¿¡°Ô¼­ µÎµå·¯Áö°Ô ³ªÅ¸³­´Ù. À̵éÀº ÀÚ½ÅÀÌ ¿øÇÏ´Â ÇØ´äÀ» ±¸ÇÏ´Â µ¥ µµ¿òÀÌ µÈ´Ù°í ÆÇ´ÜÇÒ °æ¿ì¿¡¸¸ ÀÌ·ÐÀûÀÎ ¹®Á¦¿¡ °ü½ÉÀ» °®´Â´Ù. ÄÄÇ»Å͸¦ ÇÊ¿ä·Î ÇÏ´Â ÀÀ¿ë ºÐ¾ß°¡ ¾ø´Ù¸é ÄÄÇ»ÅÍ¿¡ ´ëÇÑ Èï¹Ìµµ ¾øÀ» °ÍÀÌ°í, µû¶ó¼­ ÀÌ¿Í °°Àº ÀÚ¼¼°¡ À߸øµÈ °ÍÀÌ¶ó ¸»ÇÒ ¼ö´Â ¾øÀ» °ÍÀÌ´Ù. ±×·¯³ª ÀÌ·¯ÇÑ Çö½Ç ÁöÇâÀûÀÎ °æÇâ¿¡¼­µµ, "¿Ö ÀÌ·ÐÀ» °øºÎÇϴ°¡?" °°Àº Áú¹®ÀÌ Á¦±âµÉ ¼ö ÀÖÀ» °ÍÀÌ´Ù.

ÀÌ¿¡ ´ëÇÑ Ã¹ ¹ø° ´äÀ¸·Î ÀÌ·ÐÀº Çй® ºÐ¾ß¿¡ ´ëÇÑ ÀϹÝÀû º»ÁúÀ» ÀÌÇØÇÒ ¼ö ÀÖµµ·Ï °³³ä (concept) °ú ¿ø¸® (principle) ¸¦ Á¦°øÇÑ´Ù´Â Á¡À» µé ¼ö ÀÖ´Ù. ÄÄÇ»ÅÍ °úÇÐ ºÐ¾ß´Â Çϵå¿þ¾î ¼³°è¿¡¼­ºÎÅÍ ÇÁ·Î±×·¡¹Ö¿¡ À̸£±â±îÁö ³ÐÀº ¹üÀ§ÀÇ ´Ù¾çÇÑ ÅäÇȵéÀ» Æ÷ÇÔÇÏ´Â Çй® ºÐ¾ßÀÌ´Ù. ½Ç¼¼°è¿¡¼­ÀÇ ÄÄÇ»Å͸¦ »ç¿ëÇÏ´Â µ¥ À־ ¼º°øÀûÀÎ ÀÀ¿ëÀ» À§ÇÏ¿© ¹è¿ö¾ßÇÒ ¸¹Àº ƯÁ¤ ¼¼ºÎ»çÇ×µéÀÌ ÀÖ¾î¾ß ÇÑ´Ù. µû¶ó¼­ ÄÄÇ»ÅÍ °úÇÐÀº ¸Å¿ì ´Ù¾çÇÏ°í ±¤¹üÀ§ÇÑ Çй® ºÐ¾ßÀÌ´Ù. ÀÌ·¯ÇÑ ´Ù¾ç¼º¿¡µµ ºÒ±¸ÇÏ°í ÄÄÇ»ÅÍ °úÇÐ ºÐ¾ß¿¡´Â ¸î °¡Áö °øÅëÀûÀÎ ±âº» ¿ø¸®°¡ Á¸ÀçÇϸç, ÀÌ·¯ÇÑ ±âº» ¿ø¸®¸¦ °øºÎÇϱâ À§Çؼ­ ¿ì¸®´Â ÄÄÇ»ÅÍ¿Í °è»ê (computers and computation) ¿¡ ´ëÇÑ Ãß»óÀû ¸ðµ¨ (abstract model) À» ¼³Á¤ÇÏ´Â °ÍÀÌ´Ù. ÀÌ·¸°Ô ¼³Á¤µÇ´Â ¸ðµ¨Àº Çϵå¿þ¾î ¹× ¼ÒÇÁÆ®¿þ¾î¿¡¼­ °øÅëÀûÀ¸·Î ³ªÅ¸³ª´Â Ư¡µé, ±×¸®°í ÄÄÇ»Å͸¦ »ç¿ëÇÏ¿© ÀÛ¾÷À» ÁøÇàÇÏ´Â µ¿¾È Á¢ÇÏ°Ô µÇ´Â ¸¹Àº º¹ÀâÇÑ »çÇ׵鿡 ÇʼöÀûÀÌ°í Áß¿äÇÑ Æ¯Â¡µéÀ» ¸ðµÎ Ç¥ÇöÇÑ´Ù. ºñ·Ï ÀÌ·¯ÇÑ ¸ðµ¨µéÀº ½Ç¼¼°è¿¡ Áï½Ã Àû¿ëµÇ±â¿¡´Â ³Ê¹« ´Ü¼øÇÏÁö¸¸, À̸¦ °øºÎÇÔÀ¸·Î½á ¿ì¸®°¡ ¾ò´Â ÅëÂû·Â¿¡ ÀÇÇØ ¿ì¸®´Â ¾ÕÀ¸·Î ÇØ¾ß ÇÒ Àϵ鿡 ´ëÇÑ ±âº»ÀûÀÎ Åä´ë¸¦ ¾ò°Ô µÇ´Â °ÍÀÌ´Ù. ÀÌ¿Í °°Àº Á¢±Ù¹æ½ÄÀº ÄÄÇ»ÅÍ °úÇÐ ºÐ¾ß¿¡¸¸ ±¹ÇѵǴ °ÍÀº ¾Æ´Ï´Ù. ¸ðµ¨ÀÇ ¼³Á¤Àº ¾î´À °úÇÐ ºÐ¾ß¿¡³ª ÇʼöÀûÀÎ °ÍÀ̸ç, ±× ºÐ¾ßÀÇ ½Ç¿ë¼ºÀº ´ëºÎºÐ °£´ÜÇϸ鼭µµ °­·ÂÇÑ À̷аú ¹ýÄ¢µéÀÌ Á¸ÀçÇϴ°¡¿¡ ´Þ·Á ÀÖ´Ù.

¸íÈ®ÇÏÁö´Â ¾ÊÁö¸¸ À§ Áú¹®¿¡ ´ëÇÑ µÎ ¹ø° ´äÀº ¿ì¸®µéÀÌ ÀÌÁ¦ºÎÅÍ °øºÎÇÒ ÀÌ·ÐÀûÀÎ °³³äµéÀÌ Áï°¢ÀûÀÌ°í Áß¿äÇÑ ºÐ¾ß¿¡ ÀÀ¿ë°¡´ÉÇÏ´Ù´Â °ÍÀÌ´Ù. µðÁöÅÐ ¼³°è³ª ÇÁ·Î±×·¡¹Ö ¾ð¾î, ÄÄÆÄÀÏ·¯ ºÐ¾ß µîÀÌ È®½ÇÇÑ ¿¹µéÀ̸ç, ÀÌ¿Ü¿¡µµ ÀÌ·ÐÀûÀÎ °³³äµéÀÌ Áï½Ã ÀÀ¿ëµÉ ¼ö ÀÖ´Â ¿©·¯ ºÐ¾ßµéÀÌ Á¸ÀçÇÑ´Ù. ÀÌ Ã¥¿¡¼­ °øºÎÇÏ´Â °³³äµéÀº ÄÄÇ»ÅÍ °úÇÐÀÇ ±âÃÊ ºÐ¾ßÀÎ ¿î¿µÃ¼Á¦ (operating system) ¿¡¼­ºÎÅÍ ÃÖÁ¾ ÀÀ¿ë ºÐ¾ß¶ó ÇÒ ¼ö ÀÖ´Â ÆÐÅÏ ÀÎ½Ä µîÀÇ ºÐ¾ß¿¡±îÁö »ç¿ëµÉ ¼ö ÀÖÀ» °ÍÀÌ´Ù.

¼¼ ¹ø° ´äÀ¸·Î, ÀÌ·Ð ºÐ¾ß¿¡¼­´Â ÁöÀûÀÎ »ç¶÷µé¿¡°Ô ¸Å¿ì ÀÚ±ØÀûÀÌ°í Àç¹ÌÀÖ´Â ÁÖÁ¦µéÀ» ´Ù·ç¸ç, ¼ö¼ö²²³¢ °°Àº ¹®Á¦µéÀ» Á¦½ÃÇÔÀ¸·Î½á µ¶ÀÚµéÀÇ °øºÎ ÀÇ¿åÀ» µ¸±º´Ù´Â Á¡À» µé ¼ö ÀÖ´Ù. ÀÌ´Â º»ÁúÀûÀ¸·Î ¹®Á¦ÇØ°á (problem-solving) À» ´Ù·ç´Â ºÐ¾ßÀ̸ç, µ¶ÀÚµéÀº ¹ãÀáÀ» ¼³ÃÄ°¡¸ç ÁÖ¾îÁø ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ½Ã°£À» ÅõÀÚÇÏ°Ô µÉ °ÍÀÌ´Ù. ¾ÕÀ¸·Î °øºÎÇϸ鼭 ÀÌ·¯ÇÑ Á¡µéÀ» µ¶ÀÚµéÀÌ ¼ö±àÇßÀ¸¸é ÇÑ´Ù.

ÀÌ Ã¥¿¡¼­´Â ÄÄÇ»ÅÍ¿Í ±× ÀÀ¿ëµéÀÇ ÇÙ½ÉÀûÀÎ ±â´ÉµéÀ» Ç¥ÇöÇÏ´Â ¸ðµ¨¿¡ ´ëÇØ °øºÎÇÏ°Ô µÈ´Ù. ƯÈ÷, ÄÄÇ»ÅÍÀÇ Çϵå¿þ¾î¸¦ ¸ðµ¨¸µÇϱâ À§ÇØ ¿ÀÅ丶Ÿ (automata, automaton) ¶ó´Â °³³äÀ» ¼Ò°³ÇÑ´Ù. ¿ÀÅ丶Ÿ¶õ µðÁöÅÐ ÄÄÇ»ÅÍ¿¡¼­ ¹Ýµå½Ã ÇÊ¿äÇÑ ±â´É ¸ðµÎ¸¦ °®Ãá ±¸Á¶ÀÌ´Ù. ¿ÀÅ丶Ÿ´Â ÀÔ·ÂÀ» ¹Þ¾ÆµéÀÌ°í, Ãâ·ÂÀ» »êÃâÇÏ°í, ¾à°£ÀÇ Àӽà ±â¾ïÀå¼Ò¸¦ °¡Áú ¼ö ÀÖÀ¸¸ç, ±×¸®°í ÀÔ·ÂÀ¸·ÎºÎÅÍ Ãâ·ÂÀ¸·ÎÀÇ º¯È¯ °úÁ¤¿¡¼­ ÇÊ¿äÇÑ °áÁ¤µéÀ» ³»¸± ¼ö ÀÖ´Ù. Çü½Ä ¾ð¾î (formal language) ¶õ ÇÁ·Î±×·¡¹Ö ¾ð¾îµéÀÇ ÀϹÝÀûÀΠƯ¼ºµéÀ» Ãß»óÈ­ÇÑ °³³äÀÌ´Ù. Çü½Ä ¾ð¾î´Â ½Éº¼ (symbol) µéÀÇ ÁýÇÕ°ú ÀÌ ½Éº¼µéÀ» Á¶ÇÕÇÏ¿© ¹®Àå (sentence) À̶ó ºÒ¸®´Â °³Ã¼¸¦ ¸¸µå´Â µ¥ »ç¿ëµÇ´Â Çü¼º±ÔÄ¢µé·Î ±¸¼ºµÈ´Ù. ´Ù½Ã ¸»Çؼ­, Çü½Ä ¾ð¾î¶õ ÀÌ Çü¼º±ÔÄ¢µé¿¡ ÀÇÇØ »ý¼ºµÇ´Â ¸ðµç ¹®ÀÚ¿­ (string) µéÀÇ ÁýÇÕÀ̶ó°íµµ ÇÒ ¼ö ÀÖ´Ù. ¿ì¸®°¡ ÀÌ Ã¥¿¡¼­ °øºÎÇÏ´Â ¸î °¡Áö Çü½Ä ¾ð¾îµéÀº ½ÇÁ¦·Î »ç¿ëµÇ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾îº¸´Ù ´Ü¼ø ÇÏÁö¸¸ ÇÁ·Î±×·¡¹Ö ¾ð¾î¿¡¼­¿Í µ¿ÀÏÇÑ ÇÙ½É ±â´ÉµéÀ» ¸¹ÀÌ °¡Áö°í ÀÖ´Ù. ¿ì¸®´Â Çü½Ä ¾ð¾î¸¦ °øºÎÇÔÀ¸·Î½á ÇÁ·Î±×·¡¹Ö ¾ð¾î¿¡ ´ëÇØ ¸¹Àº °ÍµéÀ» ¹è¿ì°Ô µÉ °ÍÀÌ´Ù. ¸¶Áö¸·À¸·Î, ¿ì¸®´Â ¾Ë°í¸®Áò (algorithm) À̶ó´Â ¿ë¾î¿¡ ´ëÇØ Á¤È®È÷ Á¤ÀÇÇÔÀ¸·Î½á ±â°èÀûÀÎ °è»ê (mechanical computation) ÀÇ °³³äÀ» °ø½ÄÈ­ÇÒ °ÍÀ̸ç, ±×·¯ÇÑ ±â°èÀû ¹æ¹ý¿¡ ÀÇÇØ Çظ¦ ãÀ» ¼ö ÀÖ´Â (ȤÀº ±×·¸Áö ¸øÇÑ) ¹®Á¦µéÀÇ Á¾·ùµé¿¡ ´ëÇØ °øºÎÇÏ°Ô µÉ °ÍÀÌ´Ù. °øºÎÇÏ´Â °úÁ¤¿¡¼­, ¿ì¸®´Â À̵é Ãß»óÈ­ °³³äµé°£ÀÇ ±ä¹ÐÇÑ °ü°è¿¡ ´ëÇØ ¾Ë°Ô µÉ °ÍÀ̸ç, ±×·ÎºÎÅÍ ¾ò¾î³¾ ¼ö ÀÖ´Â °á·Ðµé¿¡ ´ëÇØ ¿¬±¸ÇÏ°Ô µÉ °ÍÀÌ´Ù.

Á¦ 1 Àå¿¡¼­´Â, ÀÌÈÄÀÇ °øºÎ¸¦ À§ÇÑ ¹ßÆÇÀ» ÁغñÇϱâ À§ÇÏ¿© ÀÌ·¯ÇÑ ±âº» °³³äµéÀ» º¹½ÀÇÑ´Ù. 1. Àý¿¡¼­´Â, ¾ÕÀ¸·Î ÇÊ¿äÇÑ ¼öÇп¡¼­ÀÇ ÁÖ¿ä °³³äµéÀ» »ìÆ캻´Ù. °³³äÀ» Ž±¸Çϴµ¥ À־ ¸¹Àº °æ¿ì Á÷°ü (intuition) ÀÌ µµ¿òÀÌ µÇ°ÚÁö¸¸, °á·ÐÀ» À¯µµÇØ ³¾ ¶§¿¡´Â ¾ö¹ÐÇÑ ³íÁõÀ» °ÅÄ¡°Ô µÇ¸ç, ÀÌ °úÁ¤¿¡¼­ ÀüÀûÀ¸·Î´Â ¾Æ´Ï´õ¶óµµ ¼öÇÐÀûÀÎ µµ±¸µéÀ» »ç¿ëÇÏ°Ô µÉ °ÍÀÌ´Ù. À̸¦ À§ÇØ µ¶ÀÚµéÀº ÁýÇÕ·Ð (set theory) À̳ª ÇÔ¼ö (function), °ü°è (relation) µî¿¡ ´ëÇÑ ¿©·¯ °¡Áö °ü·Ã ¿ë¾îµé°ú ±âº»ÀûÀÎ °á°úµé¿¡ ´ëÇØ Àß ¾Ë°í ÀÖ¾î¾ß ÇÑ´Ù. ¶ÇÇÑ Æ®¸® (tree) ³ª ±×·¡ÇÁ (graph) ±¸Á¶µµ ÀÚÁÖ »ç¿ëµÉ °ÍÀÌ´Ù. ±×·¯³ª ¶óº§ ±×·¡ÇÁ (labeled graph) ³ª À¯Çâ ±×·¡ÇÁ (directed graph) ÀÇ Á¤ÀÇ Á¤µµ¸¸ ¾Ë°í ÀÖÀ¸¸é ¹®Á¦¾øÀ» °ÍÀÌ´Ù. ¾Æ¸¶µµ ²À ÇÊ¿äÇÑ °ÍÀº Áõ¸í °úÁ¤À» µû¶ó°¥ ¼ö ÀÖ´Â ´É·Â°ú ¿Ã¹Ù¸¥ ¼öÇÐÀû ³í¹ý¿¡ ´ëÇÑ ÀÌÇØ·ÂÀ̸ç, À̸¦ À§ÇØ ¿¬¿ª¹ýÀ̳ª ±Í³³¹ý, ±Í·ù¹ý µîÀÇ ±âº»ÀûÀÎ Áõ¸í ±â¹ýµé¿¡ Àͼ÷ÇØ¾ß ÇÑ´Ù. ÀÌ Ã¥¿¡¼­´Â µ¶ÀÚµéÀÌ ÀÌ·¯ÇÑ Á¤µµÀÇ ÇÊ¿äÇÑ ¿¹ºñÁö½ÄÀ» Áö´Ï°í ÀÖ´Ù°í °¡Á¤ÇÒ °ÍÀÌ´Ù. 1. Àý¿¡¼­´Â ¾ÕÀ¸·Î »ç¿ëµÉ ÁÖ¿ä °á°úµéÀ» º¹½ÀÇÏ°í, ÀÌÈÄ ³íÀÇ¿¡¼­ÀÇ ¼öÇÐÀû Ç¥±â¹ýµéÀ» ±ÔÁ¤Çϵµ·Ï ÇÑ´Ù.

2. Àý¿¡¼­´Â ¾ð¾î (language) ¿Í ¹®¹ý (grammar), ±×¸®°í ¿ÀÅ丶Ÿ¿Í °ü·ÃÇÑ ÁÖ¿ä °³³äµéÀ» »ìÆ캻´Ù. ÀÌ·¯ÇÑ °³³äµéÀº ÀÌ Ã¥ Àüü¿¡ °ÉÃÄ ¿©·¯ ƯÁ¤ ÇüÅ·Πº¸¿©Áú °ÍÀÌ´Ù. 3. Àý¿¡¼­´Â ÀÌ·¯ÇÑ °³³äµéÀÌ ÄÄÇ»ÅÍ °úÇп¡¼­ ¾ó¸¶³ª ³Î¸® »ç¿ëµÇ´ÂÁö¸¦ º¸À̱â À§ÇÏ¿© ¸î°¡Áö °£´ÜÇÑ ÀÀ¿ëµéÀ» ¼Ò°³ÇÑ´Ù. 2. ¿Í 3. Àý¿¡¼­ÀÇ ³íÀÇ´Â ¼öÇÐÀûÀ¸·Î ¾ö¹ÐÇϱ⠺¸´Ù´Â Á÷°üÀûÀÏ °ÍÀ̸ç, ÀÌ´Â ¾ÕÀ¸·Î ´Ù·ç°íÀÚ ÇÏ´Â °³³äµéÀ» ¿ì¼± ¸íÈ®ÇÏ°Ô µ¶Àڵ鿡°Ô Á¦½ÃÇϱâ À§Çؼ­ÀÌ´Ù. ÀÌÈÄ¿¡ °¢ °³³äµé¿¡ ´ëÇÑ º¸´Ù ¼öÇÐÀûÀÌ°í ¾ö¹ÐÇÑ Á¦½Ã°¡ ÀÖÀ» °ÍÀÌ´Ù.

1. ¼öÇÐÀû °³¿ä ¹× Ç¥±â¹ý

(1) ÁýÇÕ

ÁýÇÕÀ̶õ ¿ø¼Ò (element) µéÀÇ ¸ðÀÓÀ̸ç, ¼Ò¼Ó¼º (membership) À» Á¦¿ÜÇÑ ¾î¶² ±¸Á¶µµ °¡ÁöÁö ¾Ê´Â´Ù. x °¡ ÁýÇÕ S ÀÇ ¿ø¼ÒÀÓÀ» ³ªÅ¸³»±â À§ÇÏ¿©, "x ¡ô S" ¿Í °°ÀÌ Ç¥±âÇÑ´Ù. ¶ÇÇÑ, x °¡ ÁýÇÕ S ÀÇ ¿ø¼Ò°¡ ¾Æ´ÔÀ» ³ªÅ¸³»´Â ¹®ÀåÀº "x S" ·Î Ç¥±âµÈ´Ù. ÁýÇÕÀº Áß°ýÈ£ ({ }) ³»¿¡ ¼Ò¼Ó ¿ø¼ÒµéÀ» ¿­°ÅÇÔÀ¸·Î½á Ç¥½ÃµÈ´Ù ; ¿¹¸¦ µé¾î, Á¤¼ö 0, 1, 2 ¸¦ Æ÷ÇÔÇÏ´Â ÁýÇÕÀº ´ÙÀ½°ú °°ÀÌ º¸¿©Áø´Ù.

    S = {0, 1, 2}

ÁýÇÕÀÇ Ç¥Çö½Ã¿¡, Àǹ̰¡ ¸íÈ®ÇÑ °æ¿ì¿¡´Â »ý·« ºÎÈ£ (...) ¸¦ »ç¿ëÇÒ ¼öµµ ÀÖ´Ù. ¿¹¸¦ µé¾î, ÁýÇÕ {a, b, ..., z} ´Â ¿µ¾î ¾ËÆĺª Áß ¸ðµç ¼Ò¹®ÀÚµéÀÇ ÁýÇÕÀ» ÀǹÌÇϸç, ÁýÇÕ {2, 4, 6, ...} ´Â ¾çÀÇ Á¤¼öµé Áß Â¦¼öµéÀÇ ÁýÇÕÀ» ÀǹÌÇÑ´Ù. ÇÊ¿ä¿¡ µû¶ó¼­´Â, ¦¼öµéÀÇ ÁýÇÕÀ» ´ÙÀ½°ú °°ÀÌ º¸´Ù ¸íÈ®ÇÏ°Ô Ç¥±âÇÒ ¼öµµ ÀÖ´Ù.

    S = {i : i > 0, i ´Â ¦¼öÀÌ´Ù}                                                    (1)

À̸¦ ÀÐÀ» ¶§ "S ´Â 0 º¸´Ù Å©°í ¦¼öÀÎ ¸ðµç i µéÀÇ ÁýÇÕ" À̶ó Çϸç, À̶§ ¹°·Ð i °¡ Á¤¼öÀÓÀ» ¾Ï½ÃÀûÀ¸·Î ÀǹÌÇÑ´Ù.

¸¹ÀÌ »ç¿ëµÇ´Â ÁýÇÕ ¿¬»êµé·Î´Â ÇÕÁýÇÕ (union, ¡ú), ±³ÁýÇÕ (intersection, ¡û), Â÷ÁýÇÕ (difference, -) µîÀÌ ÀÖÀ¸¸ç ´ÙÀ½°ú °°ÀÌ Á¤ÀǵȴÙ.

    

¶Ç ´Ù¸¥ ±âº»ÀûÀÎ ÁýÇÕ ¿¬»êÀº ¿©ÁýÇÕ (complementation) ÀÌ´Ù. ÁýÇÕ S ÀÇ ¿©ÁýÇÕÀº S ¿¡ ¼ÓÇÏÁö ¾Ê´Â ¸ðµç ¿ø¼Òµé·Î ±¸¼ºµÇ¸ç, ·Î Ç¥±âµÈ´Ù. ÀÌ Àǹ̸¦ Á¤È®È÷ ÀÌÇØÇϱâ À§Çؼ­´Â, ¸ðµç °¡´ÉÇÑ ¿ø¼ÒµéÀÇ ÁýÇÕÀÎ Àüü ÁýÇÕ (universal set) U ¿¡ ´ëÇØ ¾Ë¾Æ¾ß ÇÑ´Ù. Àüü ÁýÇÕ U °¡ Á¤ÀÇµÇ°í ³ª¸é, ¿©ÁýÇÕÀº ´ÙÀ½°ú °°ÀÌ Á¤ÀÇÇÒ ¼ö ÀÖ´Ù.

    

¿ø¼Ò¸¦ °®Áö ¾Ê´Â ÁýÇÕÀº °øÁýÇÕ (empty set, null set) À̶ó ºÒ¸®¸ç, Ø À¸·Î Ç¥±âµÈ´Ù. ÁýÇÕÀÇ Á¤ÀǷκÎÅÍ ´ÙÀ½°ú °°Àº »ç½ÇµéÀ» ¾Ë ¼ö ÀÖ´Ù.

´ÙÀ½Àº DeMorgan ¹ýÄ¢À¸·Î ¾Ë·ÁÁø À¯¿ëÇÑ Ç×µî½ÄÀÌ´Ù.

                                                                              (2)

                                                                              (3)

¾î¶² ÁýÇÕ ÀÇ ¸ðµç ¿ø¼ÒµéÀÌ ÁýÇÕ S ÀÇ ¿ø¼ÒÀ̸é ÁýÇÕ À» ÁýÇÕ S ÀÇ ºÎºÐÁýÇÕ (subset) À̶ó Çϸç, À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    

¸¸ÀÏ À̸鼭 S °¡ ¿¡ Á¸ÀçÇÏÁö ¾Ê´Â ¶Ç ´Ù¸¥ ¿ø¼Ò¸¦ Æ÷ÇÔÇÏ´Â °æ¿ì À» S ÀÇ ÁøºÎºÐ ÁýÇÕ (proper subset) À̶ó Çϸç, À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    

ÁýÇÕ °ú ¿¡ °øÅëÀ¸·Î ¼ÓÇÏ´Â ¿ø¼Ò°¡ ¾ø´Â °æ¿ì, Áï Ø ÀÎ °æ¿ì¿¡´Â, µÎ ÁýÇÕÀ» ¼­·Î ¼Ò (disjoint) ¶ó ÇÑ´Ù.

ÁýÇÕ ³»ÀÇ ¿ø¼ÒÀÇ °³¼ö°¡ À¯ÇÑÇÑ °æ¿ì¿¡´Â À̸¦ À¯ÇÑ ÁýÇÕ (finite set) À̶ó Çϸç, ±×·¸Áö ¾ÊÀº °æ¿ì¿¡´Â À̸¦ ¹«ÇÑ ÁýÇÕ (infinite set) À̶ó ÇÑ´Ù. À¯ÇÑ ÁýÇÕÀÇ Å©±â (size) ¶õ ±× ÁýÇÕ ³»ÀÇ ¿ø¼ÒÀÇ °³¼ö¸¦ ÀǹÌÇϸç |S| ·Î Ç¥±âÇÑ´Ù.

º¸ÅëÀÇ °æ¿ì ÇÑ ÁýÇÕÀº ¿©·¯ °³ÀÇ ºÎºÐÁýÇÕÀ» °¡Áö°Ô µÈ´Ù. ÇÑ ÁýÇÕ S ÀÇ ¸ðµç ºÎºÐÁýÇÕµéÀÇ ÁýÇÕÀ» S ÀÇ ¸èÁýÇÕ (powerset) À̶ó Çϸç, ÀÌ´Â ·Î Ç¥±âÇÑ´Ù. µ¶ÀÚµéÀº ÀÌ ÁýÇÕÀ» ¿ø¼Ò·Î ÇÏ´Â ÁýÇÕÀÓÀ» ¾Ë ¼ö ÀÖÀ» °ÍÀÌ´Ù.

(2) ÇÔ¼ö¿Í °ü°è

ÇÔ¼ö (function) ¶õ ÇÑ ÁýÇÕÀÇ ¿ø¼Òµé °¢°¢¿¡ ´ëÇØ ´Ù¸¥ ÁýÇÕÀÇ À¯ÀÏÇÑ ¿ø¼Ò·Î ¹èÁ¤ÇÏ´Â ±ÔÄ¢À» ¸»ÇÑ´Ù. f °¡ ÇÑ ÇÔ¼ö¸¦ Ç¥½ÃÇÑ´Ù¸é, ù ¹ø° ÁýÇÕÀ» ÇÔ¼ö f ÀÇ Á¤ÀÇ¿ª (domain) À̶ó Çϸç, µÎ ¹ø° ÁýÇÕÀ» Ä¡¿ª (range) À̶ó ÇÑ´Ù. ÀÌ·¯ÇÑ ÇÔ¼ö f ¸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    

ÀÌ´Â ÇÔ¼ö f ÀÇ Á¤ÀÇ¿ªÀÌ ÀÇ ºÎºÐÁýÇÕÀÌ°í, ÇÔ¼ö f ÀÇ Ä¡¿ªÀÌ ÀÇ ºÎºÐÁýÇÕÀÓÀ» ÀǹÌÇÑ´Ù. ¸¸ÀÏ ÇÔ¼ö f ÀÇ Á¤ÀÇ¿ªÀÌ °ú °°Àº °æ¿ì¿¡´Â f ¸¦ Àüü ÇÔ¼ö (total function) ¶ó Çϸç, ±×·¸Áö ¾ÊÀº °æ¿ì¿¡´Â f ¸¦ ºÎºÐ ÇÔ¼ö (partial function) ¶ó ÇÑ´Ù.

¿©·¯ ÀÀ¿ë¿¡¼­, °ü·ÃµÈ ÇÔ¼öµéÀÇ Á¤ÀÇ¿ª°ú Ä¡¿ªÀº ¾çÀÇ Á¤¼öµéÀÇ ÁýÇÕÀÌ´Ù. ´õ¿íÀÌ, ¿ì¸®´Â ¶§¶§·Î À̵é ÇÔ¼öµéÀÌ ÀμöµéÀÇ °ªÀÌ ¾ÆÁÖ Ä¿Áú ¶§ ¾î¶»°Ô º¯È­Çϴ°¡¿¡ °ü½ÉÀÌ ÀÖ´Ù. ±×·¯ÇÑ °æ¿ì ´ëºÎºÐ ¼ºÀå·ü (growth rates) ¿¡ ´ëÇÑ ÀÌÇظ¸À¸·Î ÃæºÐÇÏ°í ÀϹÝÀûÀÎ Å©±â ¼øÀ§ (order of magnitude) Ç¥±â¹ýÀÌ »ç¿ëµÉ ¼ö ÀÖ´Ù. f(n) °ú g(n) À» Á¤ÀÇ¿ªÀÌ ¾çÀÇ Á¤¼öµéÀÇ ºÎºÐÁýÇÕÀÎ ÇÔ¼öµéÀ̶ó ÇÏÀÚ. ¸¸ÀÏ ´ÙÀ½ÀÇ ºÎµî½ÄÀ» ¸¸Á·ÇÏ´Â ¾çÀÇ »ó¼ö c °¡ Á¸ÀçÇϸé, ¸ðµç n ¿¡ ´ëÇÏ¿©,

    f(n) ¡Â cg (n)

f ÀÇ ¼øÀ§°¡ g ÀÇ ¼øÀ§º¸´Ù ³ôÁö ¾Ê´Ù°í ÇÑ´Ù. ¿ì¸®´Â À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    f(n) = O(g (n))

À̸é, f ÀÇ ¼øÀ§°¡ g ÀÇ ¼øÀ§º¸´Ù ³·Áö ¾Ê´Ù°í ÇÏ°í À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    f(n) = ¥Ø(g (n))

¸¶Áö¸·À¸·Î, ´ÙÀ½ÀÇ ºÎµî½ÄÀ» ¸¸Á·ÇÏ´Â »ó¼öµé °ú °¡ Á¸ÀçÇϸé,

    

f °¡ g ¿Í °°Àº Å©±â ¼øÀ§¸¦ °®´Â´Ù°í ÇÏ°í, À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    f(n) = ¥è(g (n))

ÀÌ·¯ÇÑ Å©±â ¼øÀ§ Ç¥±â¹ý¿¡¼­, ¿ì¸®´Â »ó¼ö °è¼ö¿Í ³·Àº ¼øÀ§ÀÇ Ç×µéÀº ¹«½ÃÇÑ´Ù. ±× ÀÌÀ¯´Â n ÀÌ Ä¿Áü¿¡ µû¶ó ±× °ªµéÀº Àüü °ª¿¡ ºñÇÏ¿© º¸Àß °Í ¾ø¾îÁö±â ¶§¹®ÀÌ´Ù.

ÇÔ¼ö´Â ´ÙÀ½°ú °°ÀÌ ¼ø¼­½ÖµéÀÇ ÁýÇÕÀ¸·Î Ç¥ÇöµÉ ¼ö ÀÖÀ¸¸ç,

    

¿©±â¼­ ´Â ÇØ´ç ÇÔ¼öÀÇ Á¤ÀÇ¿ªÀÇ ¿ø¼ÒÀÌ°í, ´Â Ä¡¿ªÀÇ ´ëÀÀ°ªÀÌ µÈ´Ù. ÀÌ¿Í °°ÀÌ ¼ø¼­ ½ÖµéÀÇ ÁýÇÕÀ¸·Î ÇÔ¼ö¸¦ Ç¥ÇöÇϱâ À§Çؼ­´Â °¢ °¡ ÀÌ ÁýÇÕ ³»¿¡¼­ ¼ø¼­½ÖÀÇ Ã¹ ¹ø° À§Ä¡¿¡ ÃÖ´ë ÇÑ ¹ø¸¸ ³ªÅ¸³ª¾ß ÇÑ´Ù. ÀÌ·¯ÇÑ Á¶°ÇÀÌ ¸¸Á·µÇÁö ¾Ê´Â °æ¿ì¿¡´Â ÀÌ ÁýÇÕÀ» ÇÔ¼ö¶ó ÇÒ ¼ö ¾øÀ¸¸ç, À̸¦ °ü°è¶ó ÇÑ´Ù. °ü°è´Â ÇÔ¼ö¸¦ º¸´Ù ÀϹÝÈ­ÇÑ °³³äÀ¸·Î¼­ ÇÔ¼ö¿¡¼­´Â Á¤ÀÇ¿ªÀÇ °¢ ¿ø¼Ò´Â Á¤È®È÷ Ä¡¿ªÀÇ ÇÑ ¿ø¼Ò¿Í ´ëÀÀÀÌ µÇÁö¸¸, °ü°è¿¡¼­´Â Ä¡¿ªÀÇ ¿©·¯ ¿ø¼ÒµéÀÌ ´ëÀÀµÉ ¼ö ÀÖ´Ù.

°ü°èÀÇ ÇÑ Á¾·ù·Î µ¿Ä¡ °ü°è (equivalence relation) ¸¦ µé ¼ö Àմµ¥ ÀÌ´Â µî°¡ (equality, identity) ÀÇ °³³äÀ» ÀϹÝÈ­ÇÑ °³³äÀÌ´Ù. ÇϳªÀÇ ¼ø¼­½Ö (x, y) °¡ µ¿Ä¡ °ü°èÀÓÀ» Ç¥½ÃÇϱâ À§ÇØ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    x ¡Õ y

¿©±â¼­ ¡Õ ·Î Ç¥±âµÇ´Â °ü°è´Â ´ÙÀ½°ú °°Àº ¼¼ °¡Áö ¼ºÁúÀ» ¸¸Á·ÇÏ´Â °æ¿ì µ¿Ä¡ °ü°è¶ó ÇÑ´Ù : ¹Ý»ç¼º (reflexivity rule)

    ¸ðµç x ¿¡ ´ëÇØ, x ¡Õ x

´ëĪ¼º (symmetry rule)

    x ¡Õ y À̸é y ¡Õ x ÀÌ´Ù.

ÀüÀ̼º (transitivity rule)

    x ¡Õ y ÀÌ°í y ¡Õ z À̸é, x ¡Õ z ÀÌ´Ù.

(3) ±×·¡ÇÁ¿Í Æ®¸®

±×·¡ÇÁ¶õ µÎ °³ÀÇ À¯ÇÑ ÁýÇÕ, Áï Á¤Á¡ (vertex) µéÀÇ ÁýÇÕ °ú °£¼± (edge) µéÀÇ ÁýÇÕ À¸·Î ÀÌ·ç¾îÁö´Â ±¸Á¶¸¦ ¸»ÇÑ´Ù. ¿©±â¼­ °¢ °£¼±Àº ÁýÇÕ V ¿¡ ÀÖ´Â Á¤Á¡µéÀÇ ½ÖÀ̸ç, ¿¹¸¦ µé¾î, °£¼±

    

´Â Á¤Á¡ ·ÎºÎÅÍ Á¤Á¡ ·ÎÀÇ °£¼±ÀÌ µÈ´Ù. ÀÌ °æ¿ì °£¼± ´Â ¸¦ ±âÁØÀ¸·Î ÇßÀ» ¶§´Â ÁøÃâ °£¼± (outgoing edge) À̶ó Çϸç, ¸¦ ±âÁØÀ¸·Î ÇßÀ» ¶§´Â ÁøÀÔ °£¼± (incoming edge) À̶ó ÇÑ´Ù. ÀÌ¿Í °°Àº ±¸Á¶´Â °¢ °£¼±¿¡ ¹æÇâ (¿¹¸¦ µé¾î, ·ÎºÎÅÍ ·Î) À» ÁöÁ¤ÇϹǷΠÀ¯Çâ ±×·¡ÇÁ (directed graph, digraph) ¶ó ÇÑ´Ù. ±×·¡ÇÁ¸¦ ±¸¼ºÇÏ´Â ¿ä¼Ò, Áï Á¤Á¡À̳ª °£¼±¿¡ ¶óº§ (label) À» ÁöÁ¤ÇÒ ¼ö ÀÖÀ¸¸ç, ÀÌ·¯ÇÑ ±×·¡ÇÁ¸¦ ¶óº§ ±×·¡ÇÁ (labeled graph) ¶ó ÇÑ´Ù. ÀÌ·¯ÇÑ ¶óº§Àº Ưº°ÇÑ À̸§À̳ª ¶Ç´Â ´Ù¸¥ Á¤º¸ÀÏ ¼öµµ ÀÖ´Ù.

±×·¡ÇÁ´Â ´ÙÀ̾î±×·¥À¸·Î Æí¸®ÇÏ°Ô µµ½ÄÈ­ÇÒ ¼ö ÀÖ´Ù. ¿©±â¼­ Á¤Á¡Àº ¿øÀ¸·Î, ±×¸®°í °£¼±Àº µÎ Á¤Á¡µéÀ» ÀÕ´Â È­»ì·Î Ç¥ÇöµÈ´Ù. ¿¹¸¦ µé¾î, Á¤Á¡µéÀÇ ÁýÇÕÀÌ ÀÌ°í °£¼±µéÀÇ ÁýÇÕÀÌ ÀÎ ±×·¡ÇÁ´Â ±×¸² 1 °ú °°ÀÌ ±×·ÁÁú ¼ö ÀÖ´Ù.

±×¸² 1

ÀϹÝÀûÀ¸·Î °ú °°ÀÌ Ç¥ÇöµÇ´Â °£¼±µéÀÇ ¼ø¼­¿­À» ·ÎºÎÅÍ À¸·ÎÀÇ º¸Çà (walk) À̶ó Çϸç, º¸ÇàÀÇ ±æÀÌ (length) ´Â º¸ÇàÀÇ ½ÃÀÛ Á¤Á¡À¸·ÎºÎÅÍ ¸¶Áö¸· Á¤Á¡±îÁö Áö³ª°Ô µÇ´Â °£¼±µéÀÇ ¼öÀÌ´Ù. ¾î´À °£¼±µµ Áߺ¹ÇÏ¿© Áö³ªÁö ¾Ê´Â º¸ÇàÀ» °æ·Î (path) ¶ó Çϸç, ¶ÇÇÑ ¾î´À Á¤Á¡µµ Áߺ¹ÇÏ¿© Áö³ªÁö ¾Ê´Â °æ·Î¸¦ ´Ü¼ø °æ·Î (simple path) ¶ó ÇÑ´Ù. Á¤Á¡ ·ÎºÎÅÍ ¾î´À °£¼±µµ Áߺ¹ÇÏ¿© Áö³ªÁö ¾Ê°í Àڽſ¡°Ô·Î µ¹¾Æ¿À´Â º¸ÇàÀ» ¸¦ ±âÁö (base) ·Î ÇÏ´Â »çÀÌŬ (cycle) À̶ó ÇÑ´Ù. ÇÑ »çÀÌŬ¿¡¼­ ±âÁö Á¤Á¡ ¿ÜÀÇ ¾î´À Á¤Á¡µµ Áߺ¹ÇÏ¿© Áö³ªÁö ¾Ê´Â °æ¿ì À̸¦ ´Ü¼ø »çÀÌŬ (simple cycle) À̶ó ÇÑ´Ù. ±×¸² 1 ¿¡¼­ , ´Â Á¤Á¡ À¸·ÎºÎÅÍ Á¤Á¡ ·ÎÀÇ ´Ü¼ø °æ·ÎÀÌ´Ù. ¶ÇÇÑ, ÀÌ ±×¸²¿¡¼­ Àº »çÀÌŬÀÌÁö¸¸, ´Ü¼ø »çÀÌŬÀº ¾Æ´Ï´Ù. ±×·¡ÇÁÀÇ °£¼±¿¡ ¶óº§À» ÁöÁ¤ÇÏ´Â °æ¿ì º¸ÇàÀÇ ¶óº§ (label of a walk) À̶ó´Â °³³äÀ» »ý°¢ÇÒ ¼ö ÀÖÀ¸¸ç, ÀÌ´Â °æ·Î¸¦ Áö³ª´Â µ¿¾È °æÀ¯ÇÏ°Ô µÇ´Â °£¼± ¶óº§µéÀÇ ¼ø¼­¿­ÀÌ µÈ´Ù. ¸¶Áö¸·À¸·Î, ÇÑ Á¤Á¡¿¡¼­ ÀÚ±âÀÚ½ÅÀ¸·ÎÀÇ °£¼±À» ·çÇÁ (loop) ¶ó ÇÑ´Ù.

¶§¿¡ µû¶ó¼­´Â µÎ °³ÀÇ Á¤Á¡°£¿¡ Á¸ÀçÇÏ´Â ¸ðµç ´Ü¼ø °æ·Î (¶Ç´Â ÇϳªÀÇ Á¤Á¡À» ±âÁö·Î ÇÏ´Â ¸ðµç ´Ü¼ø »çÀÌŬ) ¸¦ ã¾Æ³»´Â ¾Ë°í¸®ÁòÀÌ ÇÊ¿äÇÒ °æ¿ì°¡ ÀÖ´Ù. È¿À²¼ºÀ» °í·ÁÇÏÁö ¾Ê´Â´Ù¸é À̸¦ À§ÇØ ´ÙÀ½°ú °°Àº ¸í¹éÇÑ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÒ ¼ö ÀÖ´Ù. ¿ì¼± ÁÖ¾îÁø Á¤Á¡ ¿¡¼­ ½ÃÀÛÇÏ¿© ¸ðµç ÁøÃâ °£¼±µé, Áï À» ³ª¿­ÇÑ´Ù. ÇöÀç Á¤Á¡ ¿¡¼­ ½ÃÀÛÇÑ ±æÀÌ°¡ 1 ÀÎ ¸ðµç °æ·ÎµéÀÌ Á¤ÇØÁø´Ù. ´ÙÀ½À¸·Î ÀÌ·¸°Ô µµ´ÞÇÑ Á¤Á¡ ¿¡ ´ëÇØ, ´Ù½Ã ÁøÃâ °£¼±µéÀ» ³ª¿­Ç쵂 ÀÌ¹Ì ÇÑ ¹ø °æÀ¯ÇÑ Á¤Á¡Àº ´Ù½Ã °æÀ¯ÇÏÁö ¾Êµµ·Ï Á¦¿ÜÇÑ´Ù. ÀÌ °úÁ¤ÀÌ ³¡³ª¸é Á¤Á¡ ¿¡¼­ ½ÃÀÛÇÏ´Â ±æÀÌ°¡ 2 ÀÎ ´Ü¼ø °æ·Î°¡ ¸ðµÎ Á¤ÇØÁø´Ù. ÀÌ °úÁ¤À» ¸ðµç °æ·Î¸¦ ¾òÀ» ¶§±îÁö ¹Ýº¹ÇÑ´Ù. Á¤Á¡µéÀÇ ¼ö°¡ ´ÜÁö À¯ÇÑ °³À̱⠶§¹®¿¡, °á±¹¿¡´Â Á¤Á¡ ¿¡¼­ ½ÃÀÛÇÏ´Â ¸ðµç ´Ü¼ø °æ·Î¸¦ ³ª¿­ÇÏ°Ô µÈ´Ù. ÀÌµé °æ·Î·ÎºÎÅÍ ¿øÇÏ´Â Á¤Á¡±îÁöÀÇ ´Ü¼ø °æ·ÎµéÀ» ¼±Á¤ÇÒ ¼ö ÀÖ´Ù.

Æ®¸® (tree) ¶õ ±×·¡ÇÁÀÇ ÇÑ Á¾·ùÀÌ´Ù. Æ®¸®´Â »çÀÌŬÀ» °®Áö ¾Ê°í, ·çÆ® (root) ¶ó ºÒ¸®´Â Ưº°ÇÑ ÇϳªÀÇ Á¤Á¡À» °¡Áö´Â À¯Çâ ±×·¡ÇÁÀÌ´Ù. ÀÌ ·çÆ®·ÎºÎÅÍ´Â ´Ù¸¥ ¸ðµç ³ëµå °¢°¢À¸·Î Á¤È®È÷ ÇϳªÀÇ °æ·Î¸¸ÀÌ Á¸ÀçÇÏ¿©¾ß ÇÑ´Ù. ÀÌ Á¤ÀÇ´Â Æ®¸®ÀÇ ·çÆ®´Â ÁøÀÔ °£¼±À» °®Áö ¾ÊÀ½À» ÀǹÌÇÏ°í, ¶ÇÇÑ Æ®¸®¿¡´Â ÁøÃâ °£¼±À» °®Áö ¾Ê´Â Á¤Á¡µéÀÌ Á¸ÀçÇÔÀ» ÀǹÌÇÑ´Ù. À̵é Á¤Á¡µéÀ» Æ®¸®ÀÇ ¸®ÇÁµé (leaves) À̶ó ÇÑ´Ù. Æ®¸®¿¡¼­ ÀÓÀÇÀÇ Á¤Á¡ ·ÎºÎÅÍ ·ÎÀÇ °£¼±ÀÌ Á¸ÀçÇÏ´Â °æ¿ì ¸¦ ÀÇ ºÎ¸ð (parent) ¶ó ÇÏ°í, ¸¦ ÀÇ ÀÚ½Ä (child) À̶ó ÇÑ´Ù. Æ®¸®¿¡¼­ ÇÑ Á¤Á¡ÀÇ ·¹º§ (level) À̶õ ·çÆ®·ÎºÎÅÍ ±× ³ëµå±îÁöÀÇ °£¼±ÀÇ °³¼ö¸¦ ÀǹÌÇϸç, Æ®¸®ÀÇ ³ôÀÌ (height) ¶õ ÇØ´ç Æ®¸®ÀÇ Á¤Á¡µé Áß °¡Àå Å« ·¹º§À» °®´Â Á¤Á¡ÀÇ ·¹º§À» ÀǹÌÇÑ´Ù. ÀÌ·¯ÇÑ ¿ë¾îµéÀº ±×¸² 2 ¿¡ ¿¹½ÃµÇ¾î ÀÖ´Ù.

±×¸² 2

¶§¿¡ µû¶ó¼­´Â Æ®¸®ÀÇ °¢ ·¹º§¿¡ ÀÖ´Â ³ëµåµé¿¡ ´ëÇØ ¼ø¼­¸¦ ºÎ¿©ÇÏ´Â °æ¿ì°¡ ÀÖÀ¸¸ç, ÀÌ·¯ÇÑ °æ¿ìÀÇ Æ®¸®¸¦ ¼ø¼­ Æ®¸® (ordered trees) ¶ó ÇÑ´Ù.

±×·¡ÇÁ¿Í Æ®¸®¿¡ ´ëÇÑ º¸´Ù ±¸Ã¼ÀûÀÎ »çÇ×µéÀº ÀÌ»ê ¼öÇп¡ ´ëÇÑ ´ëºÎºÐÀÇ ¼­Àû¿¡¼­ ã¾Æº¼ ¼ö ÀÖ´Ù.

(4) Áõ¸í ±â¹ý

ÀÌ Ã¥À» Àбâ À§ÇÏ¿© ÇÊ¿ä·Î ÇÏ´Â Áß¿äÇÑ ¿ä±¸Á¶°ÇÀº Áõ¸í°úÁ¤À» ÀÌÇØÇÏ´Â ´É·ÂÀÌ´Ù. ¼öÇÐÀûÀÎ ³íÀÇ¿¡¼­, ÀÌ¹Ì ÀÎÁ¤µÈ ¿¬¿ª Ã߷еéÀÌ »ç¿ëµÈ´Ù. ¸¹Àº Áõ¸íµéÀº ´Ü¼øÈ÷ ±×·¯ÇÑ ¿¬¿ª Ãß·Ð ´Ü°èµéÀÇ ¼ø¼­¿­ÀÌ´Ù. ¾ÆÁÖ ¸¹ÀÌ »ç¿ëµÇ´Â Áõ¸í ±â¹ýÀ¸·Î´Â ±Í³³¹ý (proof by induction) °ú ±Í·ù¹ý (proof by contradiction) µî µÎ °¡Áö°¡ ÀÖÀ¸¸ç ´ÙÀ½Àº À̵鿡 ´ëÇØ °£´ÜÈ÷ »ìÆ캸±â·Î ÇÑ´Ù.

±Í³³¹ýÀ̶õ ¸î °³ÀÇ Æ¯Á¤ »ç·Ê (instance) °¡ Âü (true) À̶ó´Â »ç½Çµé·ÎºÎÅÍ ¿©·¯ ¹®ÀåµéÀÌ ÂüÀÓÀ» Ãß·ÐÇØ ³»´Â ±â¹ýÀ» ¸»ÇÑ´Ù. ÂüÀÓÀ» Áõ¸íÇÏ°íÀÚ ÇÏ´Â ¹®ÀåµéÀÇ ¼ø¼­¿­ ÀÌ ÀÖ´Ù°í ÇÏÀÚ. ¶ÇÇÑ, ´ÙÀ½ÀÌ ¼º¸³ÇÑ´Ù°í ÇÏÀÚ.

    1. ÀÓÀÇÀÇ k(k ¡Ã 1) ¿¡ ´ëÇØ ´Â ÂüÀÌ´Ù.

    2. n ¡Ã k ÀÎ ¸ðµç n ¿¡ ´ëÇؼ­ ÀÌ ÂüÀÎ »ç½ÇÀÌ °¡ ÂüÀÓÀ» ÀǹÌÇϵµ·Ï ÇÏ´Â ¹®Á¦

ÀÌ ¼ø¼­¿­¿¡ ÀÖ´Â ¸ðµç ¹®ÀåÀÌ ÂüÀÓÀ» º¸À̱â À§ÇÏ¿© ±Í³³¹ýÀ» »ç¿ëÇÒ ¼ö ÀÖ°Ô µÇ¾ú´Ù.

±Í³³¹ý¿¡ ÀÇÇÑ Áõ¸í¿¡¼­, ´ÙÀ½°ú °°Àº ÁÖÀåÀ» ÇÒ ¼ö ÀÖ´Ù : Á¶°Ç 1 ·ÎºÎÅÍ ¹®Àåµé Áß Ã¹ k °³ ¹®ÀåµéÀÌ ÂüÀÓÀ» ¾Ë ¼ö ÀÖÀ¸¸ç, ÀÌ¿¡ Á¶°Ç 2 ¿¡ ÀÇÇÏ¿© ÀÌ ÂüÀÓÀ» ¾Ë ¼ö ÀÖ°Ô µÈ´Ù. µû¶ó¼­ ¿ì¸®´Â ¹®Àåµé Áß Ã¹ k + 1 °³ ¹®ÀåµéÀÌ ÂüÀÓÀ» ¾Ë ¼ö ÀÖÀ¸¸ç, ÀÌ¿¡ Á¶°Ç 2 ¸¦ ´Ù½Ã Àû¿ëÇÏ¸é ¶Ç´Ù½Ã °¡ ÂüÀÓÀ» ÁÖÀåÇÒ ¼ö ÀÖ°Ô µÈ´Ù. °è¼ÓÇؼ­ ³ª¸ÓÁöµµ ÂüÀÓÀ» ÁÖÀåÇÒ ¼ö ÀÖ´Ù. ÀÌ °úÁ¤ÀÌ ºÐ¸íÇϱ⠶§¹®¿¡ ÀÌ·¯ÇÑ ÁÖÀåÀ» ¸í¹éÇÏ°Ô °è¼Ó ¹Ýº¹ÇÒ ÇÊ¿ä°¡ ¾ø´Ù. ÀÌ·¯ÇÑ ÀÏ·ÃÀÇ Ãß·Ð °úÁ¤Àº ¾î´À ¹®Àå±îÁö¶óµµ ¿¬ÀåµÉ ¼ö ÀÖÀ¸¸ç, °á±¹ ¸ðµç ¹®ÀåµéÀÌ ÂüÀÌ µÊÀ» º¸ÀÌ°Ô µÇ´Â °ÍÀÌ´Ù.

¿©±â¼­ ½ÃÀÛÇÏ´Â ¹®Àåµé, Áï ¤©,¤© ±Í³³¹ýÀÇ ±âÀú (basis) ¶ó Çϸç, ¹®Àå À» ·Î ¿¬°á½ÃÅ°´Â ´Ü°è¸¦ ±Í³³ ´Ü°è (inductive step) ¶ó ÇÑ´Ù. ±Í³³ ´Ü°è´Â ÀÌ ÂüÀ̶ó´Â ±Í³³ °¡Á¤ (inductive assumption) ¿¡ ÀÇÇÏ¿© ÀϹÝÀûÀ¸·Î ½±°Ô µÈ´Ù. Çü½ÄÀûÀÎ ±Í³³ ³íÁõ¿¡¼­´Â ÀÌ¿Í °°Àº ¼¼ ºÎºÐµéÀ» ¸ðµÎ ¸í¹éÇÏ°Ô º¸¿©¾ß ÇÑ´Ù.

¿ì¸®´Â ÀÌ Ã¥¿¡¼­ Áõ¸íÀÇ ³¡À» Ç¥½ÃÇϱâ À§ÇÏ¿© ½Éº¼ ¡á À» »ç¿ëÇϱâ·Î ÇÑ´Ù.

¿¹Á¦ 6 ¿¡¼­ ±âÀú³ª ±Í³³ °¡Á¤, ±Í³³ ´Ü°è¸¦ È®ÀÎÇÏ´Â µ¥ À־ ¾à°£ ´ú Çü½ÄÀû (formal) ÀÎ ÇüÅ·Π±â¼úÇÏ¿´Áö¸¸, ÇʼöÀûÀ¸·Î ¾ð±ÞµÇ¾î¾ß ÇÒ »çÇ×µéÀº ¸ðµÎ ±â¼úÇÏ¿´´Ù. ¾ÕÀ¸·ÎÀÇ ³íÀÇ°¡ Áö³ªÄ¡°Ô Çü½ÄÀûÀÌ µÇ´Â °ÍÀ» ÇÇÇϱâ À§ÇÏ¿© ¿¹Á¦ 6 ¿¡¼­ µû¸¥ ÇüÅÂÀÇ ¼­¼ú ¹æ¹ýÀ» ÁÖ·Î »ç¿ëÇÒ °ÍÀÌ´Ù. ¸¸ÀÏ µ¶ÀÚµéÀÌ Áõ¸íÀ» ÀÌÇØÇϰųª ±¸¼ºÇÏ´Â µ¥ ÀÖ¾î ¾î·Á¿òÀÌ ÀÖ´Ù¸é ¿¹Á¦ 5 ¿¡¼­ ¼­¼úÇÑ °Íó·³ º¸´Ù Çü½ÄÀûÀÌ°í ¸íÈ®ÇÑ ¹æ¹ýÀ» »ç¿ëÇϱ⠹ٶõ´Ù.

±Í³³Àû Ãß·Ð (inductive reasoning) Àº ÀÌÇØÇϱ⠾î·Á¿ï ¼ö ÀÖÁö¸¸, ±Í³³¹ý°ú ÇÁ·Î±×·¡¹Ö¿¡¼­ »ç¿ëµÇ´Â ¼øȯ (Àç±Í, recursion) °³³ä°£ÀÇ ¹ÐÁ¢ÇÑ ¿¬°ü¼ºÀ» ¾Ë ¼ö ÀÖ°Ô ÇØÁØ´Ù. ¿¹¸¦ µé¾î, n À» ¾çÀÇ Á¤¼ö¶ó ÇÒ ¶§ ÀÓÀÇÀÇ ÇÔ¼ö f(n) ¿¡ ´ëÇÑ ¼øȯÀû Á¤ÀÇ´Â º¸Åë µÎ ºÎºÐÀ¸·Î ±¸¼ºµÈ´Ù. Çϳª´Â f(n + 1) ÀÇ Á¤ÀǸ¦ f(n), f(n - 1), ..., f(1) À¸·Î ³ªÅ¸³»´Â ºÎºÐÀ̸ç, ÀÌ´Â ±Í³³¹ýÀÇ ±Í³³ ´Ü°è¿¡ ÇØ´çÇÑ´Ù. µÎ ¹ø°·Î´Â ¼øȯÀ¸·ÎºÎÅÍ ¹þ¾î³ª´Â ºÎºÐÀε¥ ÀÌ ºÎºÐ¿¡¼­´Â f(1), f(2), ..., f(k) ¸¦ ºñ¼øȯÀûÀ¸·Î Á¤ÀÇÇÏ°Ô µÈ´Ù. ÀÌ´Â ±Í³³¹ýÀÇ ±âÀú¿¡ ÇØ´çÇÑ´Ù. ±Í³³¹ý°ú ¸¶Âù°¡Áö·Î, ¼øȯµµ ¸î¸î ÃʱⰪµé°ú ¹®Á¦ ÀÚüÀÇ ¼øȯÀû ¼Ó¼º¸¸ ÁÖ¾îÁö¸é ¹®Á¦ÀÇ ¸ðµç »ç·Ê (instance) µé¿¡ ´ëÇÑ °á·ÐÀ» À¯µµÇØ ³¾ ¼ö ÀÖµµ·Ï ÇÑ´Ù.

±Í·ù¹ýÀº ´Ù¸¥ ¸ðµç °æ¿ì°¡ ¼º¸³µÇÁö ¾ÊÀ» ¶§ ÀÚÁÖ »ç¿ëµÇ´Â ¶Ç ´Ù¸¥ °­·ÂÇÑ Áõ¸í ±â¹ýÀÌ´Ù. ¾î¶² ¹®Àå P °¡ ÂüÀÓÀ» Áõ¸íÇÏ°íÀÚ ÇÑ´Ù°í ÇÏÀÚ. À̶§ ¿ì¼± P °¡ °ÅÁþÀÌ¶ó °¡Á¤ÇÏ°í ±× °¡Á¤À¸·Î ÀÎÇØ ¾î¶² »ç½ÇµéÀÌ À¯µµµÇ´ÂÁö¸¦ È®ÀÎÇÑ´Ù. ¸¸ÀÏ, ÀÌ °¡Á¤À¸·Î ÀÎÇØ Æ²¸° °á·ÐÀÌ À¯µµµÈ´Ù¸é óÀ½ÀÇ °¡Á¤ÀÌ À߸øµÇ¾ú´Ù°í ÆÇ´ÜÇÒ ¼ö ÀÖÀ¸¸ç, µû¶ó¼­ P °¡ ÂüÀ̾î¾ß ÇÑ´Ù°í °á·ÐÁþ°Ô µÇ´Â °ÍÀÌ´Ù. ´ÙÀ½Àº °íÀüÀûÀ̸鼭µµ ¸ÚÁø ±Í·ù¹ýÀÇ ¿¹Á¦ÀÌ´Ù.

ÀÌ ¿¹Á¦´Â ±Í·ù¹ýÀÇ ÇÙ½ÉÀûÀÎ ³»¿ëÀ» º¸¿©ÁÖ°í ÀÖ´Ù. ¾î¶² °¡Á¤À» ÇÔÀ¸·Î½á ¿ì¸®´Â ±× °¡Á¤ÀÇ ¸ð¼ø ¶Ç´Â ÀÌ¹Ì °ÅÁþÀ¸·Î ¾Ë·ÁÁø »ç½Ç¿¡ µµ´ÞÇÏ°Ô µÈ´Ù. ±× À¯µµ °úÁ¤ÀÇ ¸ðµç ´Ü°è°¡ ³í¸®ÀûÀ¸·Î Ʋ¸²ÀÌ ¾ø´Ù¸é, ¿ì¸®´Â Ãʱ⠰¡Á¤ÀÌ À߸øµÇ¾úÀ½À» °á·ÐÁþ°Ô µÇ´Â °ÍÀÌ´Ù.

¿¬½À¹®Á¦

1. ÁýÇÕ S ÀÇ Å©±â¿¡ ´ëÇÑ ±Í³³¹ýÀ» »ç¿ëÇÏ¿© ÁýÇÕ S °¡ À¯ÇÑ ÁýÇÕÀ̸é ÀÓÀ» Áõ¸íÇ϶ó.

2. ÁýÇÕ °ú °¡ À¯ÇÑ ÁýÇÕÀÌ°í, ÀÌ°í, ÀÏ ¶§ ´ÙÀ½À» Áõ¸íÇ϶ó.

3. ÁýÇÕ °ú °¡ À¯ÇÑ ÁýÇÕÀ̸é, ÀÓÀ» Áõ¸íÇ϶ó.

4. ¾Æ·¡¿Í °°ÀÌ Á¤ÀÇµÈ µÎ ÁýÇÕ »çÀÌÀÇ °ü°è°¡ µ¿Ä¡ °ü°èÀÓÀ» Áõ¸íÇ϶ó.

         ÀÌ°í ¿ÀÁ÷ ±×·² ¶§¿¡¸¸

5. ½Ä (2) ¿Í ½Ä (3), Áï DeMorgan ÀÇ ¹ýÄ¢À» Áõ¸íÇ϶ó.

6. °æ¿ì¿¡ µû¶ó¼­´Â ÇÕÁýÇÕ°ú ±³ÁýÇÕ ¿¬»ê ±âÈ£¸¦ ÇÕ»ê ±âÈ£ÀÎ ¥Ò ¿Í À¯»çÇÑ ÇüÅ·Π»ç¿ëÇϱ⵵ ÇÑ´Ù. À̸¦ ÇÕÁýÇÕ¿¡ ´ëÇؼ­´Â ´ÙÀ½°ú °°ÀÌ Á¤ÀÇÇϸç, ±³ÁýÇÕ¿¡ ´ëÇؼ­µµ ºñ½ÁÇÏ°Ô Á¤ÀÇÇÑ´Ù.

    ÀÌ Ç¥±â¹ýÀ» »ç¿ëÇÏ¿©, ÀϹÝÀûÀÎ DeMorgan ÀÇ ¹ýÄ¢À» ´ÙÀ½°ú °°ÀÌ ±â¼úÇÒ ¼ö ÀÖ´Ù :

    ÁýÇÕ P °¡ À¯ÇÑ ÁýÇÕÀÏ ¶§ ÀÌ µî½ÄµéÀ» Áõ¸íÇ϶ó.

7. ´ÙÀ½À» Áõ¸íÇ϶ó.

        

8. ´ÙÀ½À» Áõ¸íÇ϶ó.

         ÀÌ°í ¿ÀÁ÷ ±×·² ¶§¿¡¸¸

9. ´ÙÀ½À» Áõ¸íÇ϶ó.

        

10. ´ÙÀ½À» Áõ¸íÇ϶ó.

        

11. À̸é, ÀÓÀ» Áõ¸íÇ϶ó.

12. µÎ ÁýÇÕ °ú ¿¡ ´ëÇØ ´ÙÀ½À» ¸¸Á·Çϱâ À§ÇÑ ÇÊ¿äÃæºÐ Á¶°ÇÀ» Á¦½ÃÇ϶ó.

        

13. f(n) = O(g (n)) ÀÌ°í g(n) = O(f (n)) À̸é, f(n) = ¥è(g (n)) ÀÓÀ» Áõ¸íÇ϶ó.

14. ÀÌÁö¸¸ ÀÓÀ» Áõ¸íÇ϶ó.

15. ´ÙÀ½ÀÇ Å©±â ¼øÀ§¿¡ ´ëÇÑ °á°ú°¡ ¼º¸³ÇÔÀ» Áõ¸íÇ϶ó.

        (a)

        (b)

        (c)

16. f(n) = O(g (n)) ÀÌ°í g(n) = O(h (n)) À̸é f(n) = O(h (n)) ÀÓÀ» Áõ¸íÇ϶ó.

17. ÀÌ°í ÀÌ¸é ´ÙÀ½ÀÌ ¼º¸³ÇÔÀ» Áõ¸íÇ϶ó.

        

18. ¿¬½À¹®Á¦ 17 ¿¡¼­, g(n) / f(n) = O(n) µµ ¼º¸³Çϴ°¡?

19. °ú À̶ó ÇÏÀÚ. ´ÙÀ½ÀÇ ÁÖÀå¿¡¼­ ¹«¾ùÀÌ À߸øµÇ¾ú´Â°¡?

        

    µû¶ó¼­

        

    ÀÌ´Ù. ±×·¯¹Ç·Î,

        f(n) - g(n) = O(n)

    ÀÌ´Ù.

20. Á¤Á¡µéÀÇ ÁýÇÕÀÌ ÀÌ°í °£¼±µéÀÇ ÁýÇÕÀÌ ÀÎ ±×·¡ÇÁ¸¦ ±×¸²À¸·Î ±×·Áº¸¾Æ¶ó. ¶ÇÇÑ ÀÌ ±×·¡ÇÁ¿¡¼­ À» ±âÁö·Î ÇÏ´Â »çÀÌŬµéÀ» ¸ðµÎ ¿­°ÅÇ϶ó.

21. ±×·¡ÇÁ G = (V, E) ¿¡ ´ëÇØ ´ÙÀ½ ÁÖÀåÀ» Áõ¸íÇ϶ó : ÀÌ ±×·¡ÇÁÀÇ Á¤Á¡µé ¿Í °°¿¡ º¸ÇàÀÌ Á¸ÀçÇϸé, ÀÌ µÎ Á¤Á¡°£¿¡´Â ±æÀÌ°¡. |V| - 1 ÀÌÇÏÀÎ °æ·Î°¡ ¹Ýµå½Ã Á¸ÀçÇÑ´Ù.

22. ¾î´À µÎ Á¤Á¡ »çÀÌ¿¡µµ ÃÖ´ë ÇϳªÀÇ °£¼±ÀÌ Á¸ÀçÇÏ´Â ±×·¡ÇÁ¿¡ ´ëÇØ ÀÌ ±×·¡ÇÁ¿¡ n °³ÀÇ Á¤Á¡ÀÌ Á¸ÀçÇÒ °æ¿ì °£¼±ÀÇ ÃÖ´ë °³¼ö´Â ÀÓÀ» Áõ¸íÇ϶ó.

23. ´ÙÀ½ÀÇ ½ÄÀ» Áõ¸íÇ϶ó.

        

24. ´ÙÀ½À» Áõ¸íÇ϶ó.

        

25. ¸ðµç n ¡Ã 4 ¿¡ ´ëÇØ, ºÎµî½Ä ÀÌ ¼º¸³ÇÔÀ» º¸¿©¶ó.

26. ÀÌ À¯¸®¼ö°¡ ¾Æ´ÔÀ» Áõ¸íÇ϶ó.

27. °¡ ¹«¸®¼öÀÓÀ» Áõ¸íÇ϶ó.

28. ´ÙÀ½ÀÇ ¹®ÀåÀÌ ÂüÀÎÁö ¾Æ´ÑÁö¸¦ Áõ¸íÇ϶ó.

        (a) À¯¸®¼ö¿Í ¹«¸®¼öÀÇ ÇÕÀº ¹«¸®¼öÀ̾î¾ß ÇÑ´Ù.

        (b) ¾ç¼öÀÎ µÎ ¹«¸®¼öÀÇ ÇÕÀº ¹«¸®¼öÀ̾î¾ß ÇÑ´Ù.

        (c) À¯¸®¼ö¿Í ¹«¸®¼öÀÇ °öÀº ¹«¸®¼öÀ̾î¾ß ÇÑ´Ù.

29. ¸ðµç ¾çÀÇ Á¤¼ö´Â ¼Ò¼ö (prime number) µéÀÇ °öÀ¸·Î ³ªÅ¸³¾ ¼ö ÀÖÀ½À» Áõ¸íÇ϶ó.

30. ¸ðµç ¼Ò¼öµéÀÇ ÁýÇÕÀÌ ¹«ÇÑ ÁýÇÕÀÓÀ» Áõ¸íÇ϶ó.

31. ¼Ò¼ö ½Ö (prime pair) Àº Â÷ÀÌ°¡ 2 ÀÎ µÎ °³ÀÇ ¼Ò¼öµé·Î ±¸¼ºµÈ´Ù. ¼Ò¼ö ½ÖµéÀº ¿©·¯ °³ ÀÖ´Ù. ¿¹¸¦ µé¾î, 11 °ú 13, 17 °ú 19, µîµî. ¼Ò¼ö ¼¼ ¿ø¼Ò ½Ö (prime triplet) Àº ¸ðµÎ°¡ ¼Ò¼öÀÎ ¼¼ °³ÀÇ ¼öµé n, n + 2, n + 4 ·Î ±¸¼ºµÈ´Ù. ¼Ò¼ö ¼¼ ¿ø¼Ò ½ÖµéÀº ¿ÀÁ÷ (1, 3, 5) ¿Í (3, 5, 7) ÀÓÀ» Áõ¸íÇ϶ó.

2. ¼¼ °¡Áö ±âÃÊ °³³ä

ÀÌ Ã¥¿¡¼­ ´Ù·ç´Â ¼¼ °¡Áö ÁÖ¿äÇÑ ÁÖÁ¦´Â ¾ð¾î (languages), ¹®¹ý (grammars), ±×¸®°í ¿ÀÅ丶Ÿ (automata) µîÀÌ´Ù. ¿ì¸®´Â ÀÌ·¯ÇÑ °³³äµé°ú °¢ °³³äµé°£ÀÇ °ü°è¿¡ ´ëÇØ ±íÀÌ °øºÎÇÏ°Ô µÉ °ÍÀ̸ç, º» Àý¿¡¼­´Â ¿ì¼± °¢ ¿ë¾îµéÀÇ Àǹ̸¦ ÀÌÇØÇÏ°íÀÚ ÇÑ´Ù.

(1) ¾ð¾î

µ¶ÀÚµéÀº ÀÌ¹Ì ¿µ¾î, ºÒ¾î, Çѱ¹¾î µî°ú °°Àº ÀÚ¿¬ ¾ð¾î (natural languages) ÀÇ °³³ä°ú´Â Ä£¼÷ÇÒ °ÍÀÌ´Ù. ÇÏÁö¸¸, ¿ì¸®µé ´ëºÎºÐÀº "¾ð¾î" ¶ó´Â ´Ü¾î°¡ ¹«¾ùÀ» ÀǹÌÇÏ´ÂÁö¿¡ ´ëÇØ Á¤È®È÷ ¼³¸íÇϱ⠾î·Á¿ï °ÍÀÌ´Ù. »çÀü¿¡¼­´Â ¾ð¾î¸¦ ¾î¶² »ý°¢À̳ª »ç½Ç, °³³äµéÀ» Ç¥ÇöÇÒ ¼ö ÀÖµµ·Ï ÇØÁÖ´Â, ½Éº¼µéÀÇ ÁýÇÕ°ú ½Éº¼À» ´Ù·ç´Â ±ÔÄ¢µéÀÇ ÁýÇÕÀ» ¼ö¹ÝÇÏ´Â, ½Ã½ºÅÛÀ̶ó°í ºñÇü½ÄÀûÀÎ Á¤ÀǸ¦ ³»¸®°í ÀÖ´Ù. ÀÌ·¯ÇÑ Çؼ³ÀÌ ¾ð¾î°¡ ¹«¾ùÀÎÁö¿¡ ´ëÇØ Á÷°üÀûÀÎ ÀÌÇظ¦ µµ¿ï ¼ö´Â ÀÖ°ÚÀ¸³ª Çü½Ä ¾ð¾î (formal languages) ¿¡ ´ëÇÑ °øºÎ¸¦ À§ÇÑ Á¤ÀǷμ­´Â ÃæºÐÄ¡ ¾ÊÀ¸¸ç, ¿ì¸®¿¡°Ô´Â ¾ð¾î¶ó´Â ¿ë¾î¿¡ ´ëÇÑ Á»´õ Á¤È®ÇÑ Á¤ÀÇ°¡ ÇÊ¿äÇÏ´Ù.
¿ì¼± ¾ËÆĺª (alphabet) À̶ó´Â ¿ë¾î¸¦ »ý°¢ÇØ º¸ÀÚ. ¾ËÆĺªÀ̶õ Çϳª ÀÌ»óÀÇ ½Éº¼µéÀÇ À¯ÇÑ ÁýÇÕÀ̸ç, º¸Åë ¥Ò ·Î Ç¥ÇöÇÑ´Ù. °³°³ÀÇ ½Éº¼µé·ÎºÎÅÍ ¹®ÀÚ¿­ (string) À» ¸¸µé ¼ö ÀÖÀ¸¸ç, ÀÌ´Â ÁÖ¾îÁø ¾ËÆĺª¿¡ ¼ÓÇÑ ½Éº¼µéÀÇ À¯ÇÑ ±æÀÌÀÇ ¼ø¼­¿­ÀÌ´Ù. ¿¹¸¦ µé¾î, ¾ËÆĺªÀÌ ¥Ò = {a, b} ¶ó¸é, abab ³ª aaabbba µîÀº ¾ËÆĺª ¥Ò ¿¡ ´ëÇÑ ¹®ÀÚ¿­ÀÌ µÇ´Â °ÍÀÌ´Ù. ¾ÕÀ¸·Î Ưº°ÇÑ °æ¿ì¸¦ Á¦¿ÜÇÏ°í´Â ¥Ò ÀÇ ¿ø¼Ò·Î ¼Ò¹®ÀÚ a, b, c, ... µîÀ» »ç¿ëÇÒ °ÍÀ̸ç, ¹®ÀÚ¿­ÀÇ À̸§À¸·Î´Â u, v, w, ... µîÀ» »ç¿ëÇÒ °ÍÀÌ´Ù. ¿¹¸¦ µé¾î, ´ÙÀ½Àº À̸§ÀÌ w ÀÎ ¹®ÀÚ¿­ÀÇ °ªÀÌ abaaa ÀÓÀ» ³ªÅ¸³½´Ù.

µÎ ¹®ÀÚ¿­ w ¿Í v ÀÇ Á¢ÇÕ (concatenation) Àº ¹®ÀÚ¿­ w ÀÇ ¿À¸¥ÂÊ¿¡ ¹®ÀÚ¿­ v ¸¦ ÀÌ¾î ºÎÃļ­ ¾ò¾îÁö´Â ¹®ÀÚ¿­ÀÌ´Ù. ¿¹¸¦ µé¾î,

    w = a1a2...an

ÀÌ°í,

    v = b1b2...bm

À̸é, w ¿Í v ÀÇ Á¢ÇÕ wv ´Â ´ÙÀ½°ú °°ÀÌ µÈ´Ù.

    wv = a1a2...anb1b2...bm

¹®ÀÚ¿­ÀÇ Àüµµ (reverse) ´Â ¹®ÀÚ¿­ ³»ÀÇ ½Éº¼µéÀ» ¿ª¼øÀ¸·Î ¹è¿­ÇÔÀ¸·Î½á ¾ò¾îÁø´Ù. ¿¹¸¦ µé¾î, w °¡ À§¿¡¼­¿Í °°Àº ¹®ÀÚ¿­À̶ó ÇÒ ¶§ ÀÌÀÇ Àüµµ wR Àº ´ÙÀ½°ú °°ÀÌ µÈ´Ù.

    wR = an...a2a1

¹®ÀÚ¿­ÀÇ w ÀÇ ±æÀÌ (length) ´Â ÇØ´ç ¹®ÀÚ¿­ ³»ÀÇ ½Éº¼µéÀÇ °³¼öÀ̸ç, |w| ·Î Ç¥±âÇÑ´Ù. ¶ÇÇÑ, ¹®ÀÚ¸¦ ÀüÇô °®Áö ¾Ê´Â ¹®ÀÚ¿­À» ºó ¹®ÀÚ¿­ (empty string) À̶ó Çϸç, ¥ë ·Î Ç¥±âÇÑ´Ù. ÀÌ¿¡ µû¶ó ¸ðµç ¹®ÀÚ¿­ w ¿¡ ´ëÇØ ´ÙÀ½ÀÇ °ü°è°¡ ¼º¸³ÇÏ°Ô µÈ´Ù :

    |¥ë| = 0
   ¥ëw = w¥ë = w

ÀÓÀÇÀÇ ¹®ÀÚ¿­ w ³»¿¡ Á¸ÀçÇÏ´Â ¿¬¼ÓÀûÀÎ ¹®ÀÚµéÀÇ ¹®ÀÚ¿­À» ºÎ¹®ÀÚ¿­ (substring) À̶ó ÇÑ´Ù. ¶ÇÇÑ, ÀÓÀÇÀÇ ¹®ÀÚ¿­ w °¡ ´ÙÀ½°ú °°ÀÌ ±¸¼ºµÇ¾î ÀÖ´Â °æ¿ì

w = vu

ºÎ¹®ÀÚ¿­ v ¿Í u ¸¦ °¢°¢ ¹®ÀÚ¿­ÀÇ w ÀÇ Á¢µÎºÎ (prefix), Á¢¹ÌºÎ (suffix) ¶ó ÇÑ´Ù. ¿¹¸¦ µé¾î, w = abbab ÀÎ °æ¿ì {¥ë, a, ab, abb, abba, abbab} ´Â w ÀÇ ¸ðµç Á¢µÎºÎµéÀÇ ÁýÇÕÀ̸ç, bab ³ª ab, b µîÀº w ÀÇ Á¢¹ÌºÎ°¡ µÈ´Ù.
±æÀÌ µî°ú °°Àº ¹®ÀÚ¿­ °ü·Ã °£´ÜÇÑ ¼ºÁúµéÀº Á÷°üÀûÀÌ°í, ¾Æ¸¶µµ ¸é¹ÐÇÏ°Ô Á¶»çÇÒ ÇÊ¿ä°¡ ¾øÀ» °ÍÀÌ´Ù. ¿¹¸¦ µé¾î v ¿Í u ¸¦ ¹®ÀÚ¿­À̶ó ÇßÀ» ¶¼ À̵éÀÇ Á¢ÇÕÀÇ ±æÀÌ´Â °¢ ¹®ÀÚ¿­µéÀÇ ±æÀÌÀÇ ÇÕ°ú °°°Ô µÇ¸ç, ´Ù½Ã ¸»Çؼ­ ´ÙÀ½ÀÌ ¼º¸³ÇÑ´Ù.

    |uv|=|u|+|v|                                                                                            (6)

ºñ·Ï ÀÌ·¯ÇÑ °ü°è¸¦ ¸íÈ®È÷ ¾Ë ¼ö ÀÖÁö¸¸, À̸¦ Á¤È®ÇÏ°Ô ÇÏ°í Áõ¸íÇÒ ¼ö ÀÖ°Ô ÇÏ´Â °ÍÀº À¯¿ëÇÏ´Ù. ±×·¸°Ô ÇÒ ¼ö ÀÖ´Â ±â¼úÀº ´õ¿í º¹ÀâÇÑ »óȲ¿¡¼­ ¸Å¿ì Áß¿äÇÏ´Ù.

¹®ÀÚ¿­ w ¿¡ ´ëÇØ Àº ¹®ÀÚ¿­ w ¸¦ n ¹ø ¹Ýº¹ÇÏ¿© ¾ò¾îÁö´Â ¹®ÀÚ¿­À» ÀǹÌÇÑ´Ù. ÀÌ¿¡ ´ëÇÑ Æ¯º°ÇÑ °æ¿ì·Î ¸ðµç ¹®ÀÚ¿­ w ¿¡ ´ëÇØ ´ÙÀ½À» Á¤ÀÇÇÑ´Ù.

    

¶ÇÇÑ, ÀÓÀÇÀÇ ¾ËÆĺª ¥Ò ¿¡ ´ëÇØ, ¥Ò ¿¡ ¼ÓÇÑ ½Éº¼µéÀ» 0 °³ ÀÌ»ó Á¢ÇÕÇÏ¿© ¾ò¾îÁö´Â ¸ðµç ¹®ÀÚ¿­µéÀÇ ÁýÇÕÀ» ¥Ò* ·Î Ç¥½ÃÇÑ´Ù.  ¥Ò* ¿¡´Â Ç×»ó ºó ¹®ÀÚ¿­ ¥ë °¡ Æ÷ÇԵǸç, ¥Ò* ¿¡¼­ ¥ë ¸¦ Á¦¿ÜÇÑ ÁýÇÕÀ» ¥Ò+ ´Â ´ÙÀ½°ú °°ÀÌ Á¤Àǵȴ٠:

    

°¡Á¤¿¡ ÀÇÇÏ¿© ¥Ò ´Â À¯ÇÑ ÁýÇÕÀÌÁö¸¸, ¥Ò* ¿Í ¥Ò+ ´Â Ç×»ó ¹«ÇÑ ÁýÇÕÀÌ µÈ´Ù. ÀÌ´Â À̵é ÁýÇÕ¿¡ ¼ÓÇÏ´Â ¹®ÀÚ¿­µéÀÇ ±æÀÌ¿¡ Á¦ÇÑÀÌ ¾ø±â ¶§¹®ÀÌ´Ù.

¾ð¾î¶õ ÀϹÝÀûÀ¸·Î ¥Ò* ÀÇ ºÎºÐÁýÇÕÀ¸·Î Á¤ÀǵǸç, ÀÓÀÇÀÇ ¾ð¾î L ¿¡ ¼ÓÇÏ´Â ¹®ÀÚ¿­À» ¾ð¾î L ÀÇ ¹®Àå (sentence) À̶ó ÇÑ´Ù. ÁÖ¾îÁø ¾ËÆĺª ¥Ò ¿¡ ´ëÇÑ ¹®ÀÚ¿­µéÀÇ ÁýÇÕµéÀº ¸ðµÎ ¾ð¾î¶ó »ý°¢ÇÒ ¼ö Àֱ⠶§¹®¿¡, ÀÌ Á¤ÀÇ´Â ¸Å¿ì ±¤¹üÀ§ÇÏ´Ù. ¾ÕÀ¸·Î ƯÁ¤ ¾ð¾î¸¦ Á¤ÀÇÇÏ´Â ¶Ç´Â ±â¼úÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ °øºÎÇÏ°Ô µÉ °ÍÀ̸ç, ÀÌ¿¡ µû¶ó Áö±Ý°ú °°Àº ±¤¹üÀ§ÇÑ °³³ä¿¡ ¾î´À Á¤µµÀÇ ¾ð¾î ±¸Á¶¼ºÀ» °¡¹ÌÇÒ ¼ö ÀÖ°Ô µÉ °ÍÀÌ´Ù. ¿ì¼± ¿©±â¼­ ¸î °¡Áö ¿¹¸¦ º¸±â·Î ÇÏÀÚ.

¾ð¾îµéÀº ÁýÇÕµéÀ̱⠶§¹®¿¡, µÎ ¾ð¾î¿¡ ´ëÇÑ ÇÕÁýÇÕ, ±³ÁýÇÕ, Â÷ÁýÇÕ µîÀÌ Á¤ÀÇµÉ ¼ö ÀÖ´Ù. ¶ÇÇÑ ¾ð¾îÀÇ ¿©ÁýÇÕÀº ¥Ò* ¸¦ ±âÁØÀ¸·Î Á¤ÀǵȴÙ. Áï L ÀÇ ¿©ÁýÇÕÀº ´ÙÀ½°ú °°ÀÌ ±â¼úÇÒ ¼ö ÀÖ´Ù.

    

ÇÑ ¾ð¾îÀÇ Àüµµ (reverse of a language) ¶õ ±× ¾ð¾î¿¡ ¼ÓÇÏ´Â ¸ðµç ¹®ÀÚ¿­µéÀÇ ÀüµµµéÀÇ ÁýÇÕÀÌ´Ù. Áï, ÀÌ ¾ð¾î¸¦ ´ÙÀ½°ú °°ÀÌ ±â¼úÇÒ ¼ö ÀÖ´Ù.

    

µÎ ¾ð¾î °ú ÀÇ Á¢ÇÕÀ̶õ ÀÇ ¿ø¼Ò¿Í ÀÇ ¿ø¼Ò¸¦ Á¢ÇÕÇÏ¿© ¾ò¾îÁú ¼ö ÀÖ´Â ¸ðµç ¹®ÀÚ¿­µéÀÇ ÁýÇÕÀ» ÀǹÌÇϸç, À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥ÇöÇÒ ¼ö ÀÖ´Ù.

    

¾î¶² ¾ð¾î L À» n ¹ø Á¢ÇÕÇÏ¿© ¾ò¾îÁö´Â ¾ð¾î¸¦ À¸·Î Ç¥½ÃÇϸç, ÀÌ¿¡ Ưº°È÷ °æ¿ì´Â ´ÙÀ½°ú °°´Ù. ¸ðµç ¾ð¾î L ¿¡ ´ëÇÏ¿©,

    

    

¸¶Áö¸·À¸·Î, ƯÁ¤ ¾ð¾î L ¿¡ ´ëÇÑ ½ºÅ¸-ÆóÆ÷ (star-closure) ´Â ´ÙÀ½°ú °°ÀÌ Á¤ÀǵǸç,

    

¾ç¼ºÆóÆ÷ (positive closure) ´Â ´ÙÀ½°ú °°ÀÌ Á¤ÀǵȴÙ.

    

(2) ¹®¹ý

¾ð¾î¿¡ ´ëÇØ ¼öÇÐÀûÀ¸·Î ¿¬±¸Çϱâ À§ÇÏ¿© ¿ì¸®´Â ¾ð¾î¸¦ ¹¦»çÇÏ´Â ¹æ¹ýÀÌ ÇÊ¿äÇÏ´Ù. ÀÏ»óÀÇ ¾ð¾îµéÀº ºÎÁ¤È®ÇÏ°í (imprecise) ¸ðÈ£Çϱâ (ambiguous) ¶§¹®¿¡, ¿µ¾î³ª Çѱ¹¾î µîÀÇ ÀÚ¿¬ ¾ð¾î¸¦ »ç¿ëÇÏ¿© ºñÇü½ÄÀûÀ¸·Î ¹¦»çÇÏ´Â °ÍÀº ÀûÀýÇÏÁö ¾Ê´Ù. ¾ÕÀ¸·Î ¿ì¸®´Â ¼­·Î ´Ù¸¥ »óȲ¿¡ Àû¿ëÇÒ ¼ö ÀÖ´Â ¿©·¯ °¡ÁöÀÇ ¾ð¾î Á¤ÀÇ ±â¹ýµéÀ» °øºÎÇÏ°Ô µÉ °ÍÀÌ´Ù. ¿©±â¼­´Â ÀϹÝÀûÀ¸·Î ¸¹ÀÌ »ç¿ëµÇ´Â °­·ÂÇÑ ±â¹ýÀÎ ¹®¹ý¿¡ ´ëÇØ ¼Ò°³ÇÑ´Ù.
ÀÚ¿¬ ¾ð¾îÀÇ ÇϳªÀÎ ¿µ¾î¿¡ ´ëÇÑ ¹®¹ýÀº ƯÁ¤ ¹®ÀåÀÌ Àû¹ýÇÏ°Ô ±¸¼ºµÇ¾ú´Â°¡¸¦ ÆÇ´ÜÇÒ ¼ö ÀÖ°Ô ÇØÁØ´Ù. ¿µ¹®¹ýÀÇ ´ëÇ¥ÀûÀÎ ±ÔÄ¢ ÁßÀÇ Çϳª´Â "¹®ÀåÀº ¸í»çÀý(noun phrase)°ú ¼úºÎ(predicate)·Î ±¸¼ºµÈ´Ù"´Â °ÍÀÌ´Ù. À̸¦ º¸´Ù Á¤È®ÇÏ°Ô ´ÙÀ½°ú °°ÀÌ Ç¥ÇöÇÒ ¼ö ÀÖ´Ù.

    <sentence> ¡æ <noun_phrase><predicate>

¹°·Ð ½ÇÁ¦ ¹®ÀåµéÀ» ´Ù·ç´Â µ¥¿¡ À־ ÀÌ ±ÔÄ¢¸¸À¸·Î´Â ÃæºÐÇÏÁö ¾Ê´Ù. À§ ±ÔÄ¢¿¡¼­ »õ·Î ¼Ò°³µÈ ±¸Á¶ÀÎ <noun_phrase>¿Í <predicate> ¿¡ ´ëÇÑ Á¤ÀÇ°¡ ¸¶·ÃµÇ¾î¾ß ÇÑ´Ù. À̸¦ ´ÙÀ½°ú °°ÀÌ Á¤ÀÇÇÏ°í,

    <noun_phrase> ¡æ <article><noun>
    <predicate> ¡æ <verb>

½ÇÁ¦·Î ´Ü¾î "a" ¿Í "the" ¸¦ <article> ¿¡, "boy" ¿Í "dog" À» <noun> ¿¡, ±×¸®°í "runs"¿Í "walks" ¸¦ <verb> ¿¡ ´ëÀÔ½ÃÅ°¸é, "a boy runs"¿Í "the dog walks" µîÀÇ ¹®ÀåÀº ÀûÀýÇÏ°Ô ±¸¼ºµÇ¾î ÀÖ´Â ¹®ÀåÀÎ °ÍÀ¸·Î ÆÇ´ÜÇÒ ¼ö ÀÖ´Ù. ¸¸ÀÏ ¿ÏÀüÇÑ ¹®¹ýÀ» Á¦°øÇÒ ¼ö¸¸ ÀÖ´Ù¸é, ÀÌ·ÐÀûÀ¸·Î ¸ðµç ÀûÀýÇÑ ¹®ÀåµéÀº ÀÌ¿Í °°Àº ¹æ½ÄÀ¸·Î ¼³¸íµÉ ¼ö ÀÖÀ» °ÍÀÌ´Ù.
ÀÌ ¿¹¿¡¼­´Â ÀϹÝÀûÀÎ °³³ä¿¡ ´ëÇØ º¸´Ù °£´ÜÇÑ °³³äµéÀ» »ç¿ëÇÏ¿© Á¤ÀÇÇÏ´Â ¹æ¹ýÀ» º¸¿©ÁÖ°í ÀÖ´Ù. Áï, ÃÖ»óÀ§ ´Ü°èÀÇ °³³ä¿¡¼­, ¿©±â¼­´Â <sentence>, ½ÃÀÛÇÏ¿© À̸¦ °è¼Ó ºÐÇØÇϸ鼭 ¸¶Áö¸·À¸·Î ´õ ÀÌ»ó ºÐÇØÇÒ ¼ö ¾ø´Â ¾ð¾î ±¸Á¶µé·Î Ç¥ÇöÇÏ´Â °ÍÀÌ´Ù. ÀÌ·¯ÇÑ °³³äÀ» ÀϹÝÈ­ÇÏ¿© Çü½Ä ¹®¹ý(formal grammar)À̶ó´Â °³³äÀÌ Á¦½ÃµÇ´Â °ÍÀÌ´Ù.

¹®¹ýÀÇ ÇÙ½ÉÀº »ý¼º±ÔÄ¢µéÀÌ´Ù ; »ý¼º±ÔÄ¢µéÀº ÇØ´ç ¹®¹ýÀÌ ¾î¶»°Ô ÇϳªÀÇ ¹®ÀÚ¿­À» ´Ù¸¥ ¹®ÀÚ¿­·Î º¯È¯Çϴ°¡¸¦ ±ÔÁ¤ÇÏ°í, ÀÌ¿¡ µû¶ó ÁÖ¾îÁø ¹®¹ý¿¡ ´ëÇÑ ¾ð¾î¸¦ Á¤ÀÇÇÏ°Ô µÇ´Â °ÍÀÌ´Ù. ¾ÕÀ¸·Î ¸ðµç »ý¼º±ÔÄ¢µéÀº ´ÙÀ½ÀÇ ÇüŸ¦ °®´Â´Ù°í °¡Á¤ÇÑ´Ù.

    x ¡æ y

¿©±â¼­ x ´Â (V¡úT)+ ÀÇ ¿ø¼ÒÀÌ°í, y ´Â (V¡úT)* ÀÇ ¿ø¼ÒÀÌ´Ù. »ý¼º±ÔÄ¢Àº ´ÙÀ½°ú °°Àº ¹æ¹ýÀ¸·Î Àû¿ëµÈ´Ù : ´ÙÀ½°ú °°Àº ÇüÅ·ΠÁÖ¾îÁø ¹®ÀÚ¿­ w ¿¡ ´ëÇϼ­

    w = uxv

ÀÌ ¹®ÀÚ¿­¿¡ »ý¼º±ÔÄ¢ x ¡æ y °¡ Àû¿ëµÉ ¼ö ÀÖÀ¸¸ç, x ¸¦ y ·Î ´ëüÇϱâ À§ÇÏ¿© »ý¼º±ÔÄ¢À» »ç¿ëÇÏ¿© ´ÙÀ½°ú °°Àº ¹®ÀÚ¿­À» ¾ò°Ô µÈ´Ù :

    z = uyv

ÀÌ·¯ÇÑ °úÁ¤À» ´ÙÀ½°ú °°ÀÌ Ç¥ÇöÇÑ´Ù.

    w ¢¡ z

ÀÌ¿¡ ´ëÇØ ¿ì¸®´Â w °¡ z ¸¦ À¯µµÇÑ´Ù (derive) °í ¸»Çϰųª ¶Ç´Â z °¡ w ·ÎºÎÅÍ À¯µµµÈ´Ù ¶ó°í ¸»ÇÑ´Ù. ¹®¹ýÀÇ »ý¼º±ÔÄ¢µéÀ» ÀÓÀÇ ¼ø¼­·Î ¿¬¼ÓÀûÀ¸·Î Àû¿ëÇÔÀ¸·Î½á °è¼Ó »õ·Î¿î ¹®ÀÚ¿­µéÀÌ À¯µµµÈ´Ù. °¢ »ý¼º±ÔÄ¢µéÀº Àû¿ë°¡´ÉÇÑ °æ¿ì¿¡ »ç¿ëµÉ ¼ö ÀÖ°í ¶ÇÇÑ ÇÊ¿äÇÑ ¸¸Å­ ¿©·¯ ¹ø Àû¿ëµÉ ¼öµµ ÀÖ´Ù. ¸¸ÀÏ ´ÙÀ½°ú °°Àº À¯µµ°¡ °¡´ÉÇÏ´Ù¸é,

    w1 ¢¡ w2 ¢¡ ¡¦ ¢¡ wn

¿ì¸®´Â w1 ÀÌ wn À» À¯µµÇÑ´Ù°í ¸»Çϸç, À̸¦ ´ÙÀ½°ú °°ÀÌ Ç¥±âÇÑ´Ù.

    w1 wn

ÀÌ Ç¥Çö¿¡¼­ * ´Â w1 À¸·ÎºÎÅÍ wn À» À¯µµÇϱâ À§ÇÏ¿© ¸í±âµÇÁö ¾ÊÀº ¼ö(0ÀÏ ¼öµµ ÀÖÀ½)ÀÇ ´Ü°è°¡ ÃëÇØÁú ¼ö ÀÖÀ½À» ÀǹÌÇÑ´Ù. µû¶ó¼­

    w w

µµ Ç×»ó ¼º¸³ÇÑ´Ù.
»ý¼º±ÔÄ¢µéÀ» ¼­·Î ´Ù¸¥ ¼ø¼­·Î Àû¿ëÇÔÀ¸·Î½á, ÁÖ¾îÁø ¹®¹ýÀº ¸¹Àº ¹®ÀÚ¿­µéÀ» »ý¼ºÇÒ ¼ö ÀÖ´Ù. ÀÌ·¯ÇÑ ¸ðµç ´Ü¸» ¹®ÀÚ¿­µéÀÇ ÁýÇÕÀ» ÁÖ¾îÁø ¹®¹ý¿¡ ÀÇÇØ »ý¼ºµÇ´Â ¶Ç´Â Á¤ÀǵǴ ¾ð¾î¶ó ÇÑ´Ù.

¸¸ÀÏ w ¡ô L(G) ÀÌ¸é ´ÙÀ½°ú °°Àº ³ª¿­À»

    S ¢¡ w1 ¢¡ w2 ¢¡ ¡¦ ¢¡ wn ¢¡ w

¹®Àå w ¿¡ ´ëÇÑ À¯µµ (derivation) ¶ó ÇÑ´Ù. ¿©±â¼­ ´Ü¸»»Ó ¾Æ´Ï¶ó º¯¼öµé·Î ±¸¼ºµÈ ¹®ÀÚ¿­ S, w1, w2, ..., wn µîÀ» ÀÌ À¯µµ¿¡¼­ÀÇ ¹®Àå ÇüÅ (sentential form) ¶ó ÇÑ´Ù.

À§ ¿¹Á¦µéÀº ´õ ÀÌ»ó ¾ð±ÞÀÌ ÇÊ¿ä ¾øÀ» Á¤µµ·Î ½¬¿î ¿¹Á¦µéÀÌ´Ù. ÇÏÁö¸¸, ÀϹÝÀûÀ¸·Î ºñÇü½ÄÀûÀ¸·Î ¹¦»çµÇ´Â ¾ð¾î¿¡ ´ëÇÑ ¹®¹ýÀ» ã¾Æ³»´Â ÀÏÀ̳ª ¶Ç´Â ÁÖ¾îÁø ¹®¹ý¿¡ ÀÇÇØ Á¤ÀǵǴ ¾ð¾î¿¡ ´ëÇØ Á÷°üÀûÀΠƯ¼ºÀ» ã¾Æ³»´Â ÀÏÀº ±×¸® ½±Áö ¾Ê´Ù. ÁÖ¾îÁø ¾ð¾î L ÀÌ Æ¯Á¤ ¹®¹ý G ¿¡ ÀÇÇØ »ý¼ºµÈ´Ù´Â »ç½ÇÀ» º¸À̱â À§Çؼ­´Â, ¿ì¼± (a) ¸ðµç ¹®ÀÚ¿­ w ¡ô L ÀÌ ¹®¹ý G ¸¦ »ç¿ëÇÏ¿© ½ÃÀÛ º¯¼ö S ·ÎºÎÅÍ À¯µµµÉ ¼ö ÀÖ´Ù´Â »ç½Ç°ú (b) ÀÌ·¸°Ô À¯µµµÇ´Â ¸ðµç ¹®ÀÚ¿­µéÀÌ ¾ð¾î L ¿¡ ¼ÓÇÑ´Ù´Â »ç½ÇÀ» Áõ¸íÇØ¾ß ÇÑ´Ù.

º¸Åë, ÁÖ¾îÁø ¾ð¾î¿¡ ´ëÇÏ¿© ±× ¾ð¾î¸¦ »ý¼ºÇÏ´Â ¹®¹ýÀÌ ¿©·¯ °³ Á¸ÀçÇÑ´Ù. ÀÌµé ¹®¹ýÀº ¼­·Î ´Ù¸£Áö¸¸, ¾î¶² ¸éÀ¸·Î´Â µ¿Ä¡ (equivalent) ÀÌ´Ù. ¿ì¸®´Â µÎ °³ÀÇ ¹®¹ý °ú °¡ ÀÌ °°Àº ¾ð¾î¸¦ »ý¼ºÇÏ´Â °æ¿ì, Áï,

    

À̸é, µÎ ¹®¹ýÀº µ¿Ä¡¶ó°í ÇÑ´Ù. ¾ÕÀ¸·Î È®ÀÎÇÏ°Ô µÇ°ÚÁö¸¸, µÎ °³ÀÇ ¹®¹ýÀÌ µ¿Ä¡ÀÓÀ» ¾Ë¾Æ³»´Â °ÍÀÌ Ç×»ó ½¬¿î °ÍÀº ¾Æ´Ï´Ù.

(3) ¿ÀÅ丶Ÿ

¿ÀÅ丶Ÿ (automaton) ¶õ µðÁöÅÐ ÄÄÇ»ÅÍ¿¡ ´ëÇÑ Ãß»óÀû ¸ðµ¨À̸ç, ¸ðµç ¿ÀÅ丶ŸµéÀº ¸î °¡Áö ÇʼöÀûÀÎ ±â´ÉµéÀ» °®´Â´Ù. ¿ì¼± ¿ÀÅ丶Ÿ´Â ÀÔ·ÂÀ» ¹Þ¾ÆµéÀÌ´Â ÀåÄ¡¸¦ °®´Â´Ù. ÀÔ·ÂÀº ÁÖ¾îÁø ¾ËÆĺª¿¡ ´ëÇÑ ¹®ÀÚ¿­ÀÌ°í ÀÔ·Â ÆÄÀÏ (input file) ¿¡ ÀúÀåµÇ¸ç, ¿ÀÅ丶Ÿ´Â À̸¦ ÀÐÀ» ¼ö´Â ÀÖÁö¸¸ º¯°æÇÒ ¼ö´Â ¾ø´Ù. ÀÔ·Â ÆÄÀÏÀº ¼¿ ´ÜÀ§·Î ±¸ºÐµÇ¸ç, °¢ ¼¿Àº ÇϳªÀÇ ½Éº¼À» ÀúÀåÇÒ ¼ö ÀÖ´Ù. ÀÔ·Â ÀåÄ¡´Â (EOF Á¶°ÇÀ» °Ë»çÇÔÀ¸·Î½á) ÀÔ·Â ¹®ÀÚ¿­ÀÇ ¸¶Áö¸·À» °¨ÁöÇÒ ¼ö ÀÖ´Ù. ¿ÀÅ丶Ÿ´Â ¾î¶² ÇüÅ·εç Ãâ·ÂÀ» »ý¼ºÇÒ ¼öµµ ÀÖ´Ù. ¶ÇÇÑ, ¿ÀÅ丶Ÿ´Â Àӽà ±â¾ïÀå¼Ò (storage) ¸¦ °¡Áú ¼ö ÀÖ´Ù. ÀÌ ±â¾ïÀå¼Ò´Â ¹«ÇÑ °³ÀÇ ¼¿µé·Î ±¸¼ºµÇ¾î ÀÖÀ¸¸ç, °¢ ¼¿Àº ÁÖ¾îÁø ¾ËÆĺª (ÀÌ´Â ¹Ýµå½Ã ÀÔ·Â ¾ËÆĺª°ú °°À» ÇÊ¿ä´Â ¾ø´Ù) ³»ÀÇ ÇÑ ½Éº¼À» ÀúÀåÇÒ ¼ö ÀÖ´Ù. ¿ÀÅ丶Ÿ´Â Á¦¾î ÀåÄ¡ (control unit) ¸¦ °¡Áø´Ù. ÀÌ Á¦¾î ÀåÄ¡´Â À¯ÇÑ °³ÀÇ ³»ºÎ »óÅ (internal state) µé Áß ÇÑ »óÅ¿¡ ÀÖÀ» ¼ö ÀÖÀ¸¸ç, ¹Ì¸® Á¤ÇØÁø ±ÔÄ¢¿¡ µû¶ó »óŸ¦ ¹Ù²Ü ¼ö ÀÖ´Ù. ±×¸² 3 Àº ÀϹÝÀûÀÎ ¿ÀÅ丶ŸÀÇ µµ½ÄÀûÀΠǥÇöÀ» º¸¿©ÁØ´Ù.

 

±×¸² 3

¿ÀÅ丶Ÿ´Â ÀÌ»ê ½Ã°£ (discrete time) ´ÜÀ§·Î ¿î¿µµÇ´Â °ÍÀ» °¡Á¤ÇÑ´Ù. ÀÓÀÇÀÇ ÁÖ¾îÁø ½Ã°£¿¡ Á¦¾î ÀåÄ¡´Â ¾î¶² ³»ºÎ »óÅ¿¡ ÀÖ°Ô µÇ¸ç, ÀÔ·Â ÀåÄ¡´Â ÀÔ·Â ÆÄÀÏÀÇ Æ¯Á¤ ½Éº¼À» ÀоîµéÀδÙ. ´ÙÀ½ ´Ü°è¿¡¼­ÀÇ Á¦¾î ÀåÄ¡ÀÇ ³»ºÎ »óÅ´ ´ÙÀ½-»óÅ ÇÔ¼ö (next-state function) ¶Ç´Â ÀüÀÌ ÇÔ¼ö (transition function) ¿¡ ÀÇÇÏ¿© °áÁ¤µÈ´Ù. ÀÌ ÀüÀÌ ÇÔ¼ö´Â ÇöÀç »óÅÂ, ÇöÀçÀÇ ÀÔ·Â ½Éº¼, ÇöÀç Àӽà ±â¾ïÀå¼Ò¿¡ ÀúÀåµÈ ³»¿ë µî¿¡ µû¶ó ´ÙÀ½ »óŸ¦ °áÁ¤ÇÑ´Ù. ÇÑ ´Ü°è¿¡¼­ ´ÙÀ½ ´Ü°è·Î ÀüÀÌ°¡ ¹ß»ýÇÏ´Â µ¿¾È Ãâ·ÂÀÌ »ý¼ºµÇ°Å³ª Àӽà ±â¾ïÀå¼ÒÀÇ ³»¿ëÀÌ º¯È­µÉ ¼ö ÀÖ´Ù. Çü»ó(configuration)À̶ó´Â ¿ë¾î´Â Á¦¾î ÀåÄ¡¿Í ÀÔ·Â ÆÄÀÏ, ±×¸®°í Àӽà ±â¾ïÀå¼ÒÀÇ »óŸ¦ Á¾ÇÕÇÏ¿© ¾ð±ÞÇÒ ¶§ »ç¿ëÇÑ´Ù. ¿ÀÅ丶Ÿ°¡ ÇÑ Çü»óÀ¸·ÎºÎÅÍ ´ÙÀ½ Çü»óÀ¸·Î ÀüÀÌÇÏ´Â °ÍÀ» À̵¿(move) À̶ó ÇÑ´Ù.

ÀÌ·¯ÇÑ ÀϹÝÀûÀÎ ¸ðµ¨Àº ¿ì¸®°¡ ÀÌ Ã¥¿¡¼­ ³íÀÇÇÏ´Â ¸ðµç ¿ÀÅ丶Ÿ¿¡ Àû¿ëµÈ´Ù. ¾î¶² °æ¿ì¿¡µµ À¯ÇÑ-»óÅ Á¦¾îÀåÄ¡ (finite-state control) ´Â °øÅëÀûÀÌÁö¸¸, Ãâ·ÂÀ» »ý¼ºÇÏ´Â ¹æ¹ýÀ̳ª Àӽà ±â¾ïÀå¼Ò¿Í °ü·ÃÇÑ ¼ºÁúÀº ¿ÀÅ丶Ÿ¸¶´Ù Â÷ÀÌ°¡ ÀÖ´Ù. Àӽà ±â¾ïÀå¼ÒÀÇ ¼ºÁúÀº °¢ ÇüÅÂÀÇ ¿ÀÅ丶Ÿ¿¡ ´ëÇØ Ä¿´Ù¶õ ¿µÇâÀ» ÁÖ°Ô µÈ´Ù.

ÀÌÈĺÎÅÍ´Â ¿ÀÅ丶Ÿ¸¦ °áÁ¤Àû ¿ÀÅ丶Ÿ (deterministic automata) ¿Í ºñ°áÁ¤Àû ¿ÀÅ丶Ÿ (nondeterministic automata) ·Î ±¸ºÐÇÒ ÇÊ¿ä°¡ ÀÖ´Ù. °áÁ¤Àû ¿ÀÅ丶Ÿ¿¡¼­´Â °¢ À̵¿ÀÌ ÇöÀçÀÇ Çü»ó¿¡ ÀÇÇØ À¯ÀÏÇÏ°Ô °áÁ¤µÈ´Ù. Áï, ¿ÀÅ丶ŸÀÇ ³»ºÎ »óÅÂ, ÀÔ·Â, ±×¸®°í Àӽà ±â¾ïÀå¼ÒÀÇ ³»¿ë µîÀÌ ¾Ë·ÁÁö¸é ±× ¿ÀÅ丶ŸÀÇ ÀÌÈÄ ÇൿÀ» Á¤È®È÷ ¿¹ÃøÇÒ ¼ö ÀÖ°Ô µÇ´Â °ÍÀÌ´Ù. ºñ°áÁ¤Àû ¿ÀÅ丶Ÿ¿¡¼­´Â ±×·¸Áö ¾Ê´Ù. ºñ°áÁ¤Àû ¿ÀÅ丶Ÿ´Â °¢ ´Ü°è¿¡¼­ ¿©·¯ °¡Áö À̵¿ÀÌ °¡´ÉÇϸç, µû¶ó¼­ Á¤È®È÷ ÇϳªÀÇ °¡´ÉÇÑ Çൿ¸¸À» ¿¹ÃøÇϱ⠺¸´Ù´Â °¡´ÉÇÑ ÇൿµéÀÇ ÁýÇÕÀ» ¿¹ÃøÇÒ ¼ö ÀÖÀ» »ÓÀÌ´Ù. ¿©·¯ ÇüÅÂÀÇ ¿ÀÅ丶Ÿ¿¡ ´ëÇÑ °áÁ¤Àû ¿ÀÅ丶Ÿ¿Í ºñ°áÁ¤Àû ¿ÀÅ丶Ÿ°£ÀÇ °ü°è´Â ¾ÕÀ¸·Î ¿ì¸®°¡ °øºÎÇÏ´Â µ¥ À־ Áß¿äÇÑ ¿ªÇÒÀ» ÇÒ °ÍÀÌ´Ù.

Ãâ·ÂÀÌ ´Ü¼øÈ÷ "yes" ¶Ç´Â "no" ·Î Á¦ÇѵǾî ÀÖ´Â ¿ÀÅ丶Ÿ¸¦ Àνıâ (accepter) ¶ó ÇÑ´Ù. ÀÔ·Â ¹®ÀÚ¿­ÀÌ ÁÖ¾îÁ³À» ¶§ Àνıâ´Â ¿À·ÎÁö ±× ¹®ÀÚ¿­À» ½ÂÀÎ (accept) Çϰųª °ÅºÎ (reject) ÇÏ´Â ¿ªÇÒ¸¸À» ¼öÇàÇÑ´Ù. À̺¸´Ù ´õ ÀϹÝÀûÀÎ ¿ÀÅ丶Ÿ·Î ÀÓÀÇÀÇ ¹®ÀÚ¿­À» Ãâ·ÂÀ¸·Î »ý¼ºÇÒ ¼ö ÀÖ´Â ¿ÀÅ丶Ÿ¸¦ º¯È¯±â (transducer) ¶ó ºÎ¸¥´Ù. ´ÙÀ½ Àý¿¡¼­ °£´ÜÇÑ º¯È¯±âÀÇ ¿¹µéÀ» Á¦½ÃÇÏ°ÚÁö¸¸, ÀÌ Àå¿¡¼­ÀÇ ÁÖµÈ °ü½ÉÀº Àνı⿡ ÀÖ´Ù.

¿¬½À¹®Á¦

1. ¸ðµç ¹®ÀÚ¿­ u ¿Í ¸ðµç n ¿¡ ´ëÇØ ÀÓÀ» »ç¿ëÇÏ¿© Áõ¸íÇ϶ó.

2. À§¿¡¼­ ºñÇü½ÄÀûÀ¸·Î ¼Ò°³µÇ¾ú´ø ¹®ÀÚ¿­ÀÇ Àüµµ´Â ´ÙÀ½°ú °°ÀÌ ¼øȯÀûÀÎ ±ÔÄ¢À» »ç¿ëÇÏ¿© º¸´Ù Á¤È®È÷ Á¤ÀÇµÉ ¼ö ÀÖ´Ù. ¸ðµç a ¡ô ¥Ò, w ¡ô ¥Ò* ¿¡ ´ëÇØ,

        

    À̸¦ ÀÌ¿ëÇÏ¿©, ¸ðµç u, v ¡ô ¥Ò+ ¿¡ ´ëÇØ, ´ÙÀ½ÀÌ ¼º¸³ÇÔÀ» Áõ¸íÇ϶ó.

        

3. ¸ðµç w ¡ô ¥Ò* ¿¡ ´ëÇØ ÀÓÀ» Áõ¸íÇ϶ó.

4. L = {ab, aa, baa} ¶ó ÇÏÀÚ. ´ÙÀ½ ¹®ÀÚ¿­µé Áß ¾î¶² °ÍÀÌ L* ¿¡ ¼ÓÇϴ°¡ : abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa?

5. ¿¹Á¦ 12 ¿Í 13 ¿¡¼­ÀÇ ¾ð¾îµéÀ» °í·ÁÇØ º¸ÀÚ. ¾î´À ¾ð¾î°¡ L = L* ¸¦ ¸¸Á·Çϴ°¡?

6. ¸¦ ¸¸Á·ÇÏ´Â ¾ð¾îµéÀÌ Á¸ÀçÇϴ°¡?

7. ¸ðµç ¾ð¾î °ú ¿¡ ´ëÇØ,

        

    ÀÓÀ» Áõ¸íÇ϶ó.

8. ¸ðµç ¾ð¾î L ¿¡ ´ëÇØ, ÀÓÀ» Áõ¸íÇ϶ó.

9. ´ÙÀ½ÀÇ ÁÖÀåÀÌ ¿ÇÀºÁö Ʋ¸°Áö¸¦ Áõ¸íÇ϶ó.

        (a) ¸ðµç ¾ð¾î °ú ¿¡ ´ëÇØ,

        (b) ¸ðµç ¾ð¾î L ¿¡ ´ëÇØ,

10. ´ÙÀ½ ¾ð¾î¸¦ »ý¼ºÇÏ´Â ¥Ò = {a, b} ¿¡ ´ëÇÑ ¹®¹ýÀ» ã¾Æ¶ó.

        (a) a ¸¦ Çϳª¸¸ °®´Â ¸ðµç ¹®ÀÚ¿­µé

        (b) a ¸¦ Çϳª ÀÌ»ó °®´Â ¸ðµç ¹®ÀÚ¿­µé

        (c) a °¡ ¼¼ °³ ÀÌÇÏÀÎ ¸ðµç ¹®ÀÚ¿­µé

        (d) a °¡ ¼¼ °³ ÀÌ»óÀÎ ¸ðµç ¹®ÀÚ¿­µé

    °¢ °æ¿ì¿¡ ´ëÇØ, ´ç½ÅÀÌ Á¦½ÃÇÑ ¹®¹ýÀÌ Á¤¸»·Î ÁöÁ¤µÈ ¾ð¾î¸¦ »ý¼ºÇÔÀ» º¸¿©¶ó.

11. ´ÙÀ½ »ý¼º±ÔÄ¢µéÀ» °®´Â ¹®¹ý¿¡ ÀÇÇÏ¿© »ý¼ºµÇ´Â ¾ð¾îÀÇ °£´ÜÇÑ ¹¦»ç¸¦ Á¦½ÃÇ϶ó.

         S ¡æ aA
   A ¡æ bS
   S ¡æ ¥ë

12. ´ÙÀ½ »ý¼º±ÔÄ¢µéÀ» °®´Â ¹®¹ýÀº ¾î¶² ¾ð¾î¸¦ »ý¼ºÇϴ°¡?

        S ¡æ Aa
   A ¡æ B
   B ¡æ Aa

13. ´ÙÀ½ °¢ ¾ð¾îµé¿¡ ´ëÇØ, ±× ¾ð¾î¸¦ »ý¼ºÇÏ´Â ¹®¹ýÀ» ã¾Æ¶ó.

        (a)

        (b)

        (c)

        (d)

        (e)

        (f)

        (g)

        (h)

        (i)

14. ¥Ò = {a} ¿¡ ´ëÇÑ ´ÙÀ½ ¾ð¾îµéÀ» »ý¼ºÇÏ´Â ¹®¹ýÀ» ã¾Æ¶ó.

        (a) L = {w : |w| mod 3 = 0}

        (b) L = {w : |w| mod 3 > 0}

        (c) L = {w : |w| mod 3 ¡Á |w| mod 2}

        (d) L = {w : |w| mod 3 ¡Ã |w| mod 2}]

15. ´ÙÀ½ ¾ð¾î¸¦ »ý¼ºÇÏ´Â ¹®¹ýÀ» ã¾Æ¶ó.

        

    ÀÚ½ÅÀÇ ´ä¿¡ ´ëÇÑ ¿Ïº®ÇÑ ±Ù°Å¸¦ Á¦½ÃÇ϶ó.

16. ¿¹Á¦ 13 ÀÇ Ç¥±â¹ýÀ» ´ÙÀ½ ¾ð¾îµé¿¡ ´ëÇÑ ¹®¹ýÀ» ã¾Æ¶ó. ¥Ò = {a, b} ¸¦ °¡Á¤ÇÑ´Ù.

        (a)

        (b)

        (c)

        (d)

17. ¥Ò = {a, b, c} ¿¡ ´ëÇØ, ¿¬½À¹®Á¦ 16(a) ¿Í 16(b) ¸¦ ´äÇ϶ó.

18. ¿¹Á¦ 14 ¿¡¼­ÀÇ ÀÌ ÁÖ¾îÁø ¾ð¾î¸¦ »ý¼ºÇÔÀ» Áõ¸íÇ϶ó.

19. ´ÙÀ½ °¢ »ý¼º±ÔÄ¢µéÀ» °®´Â µÎ °³ÀÇ ¹®¹ýÀÌ µ¿Ä¡ÀÎÁö¸¦ º¸¿©¶ó.

        S ¡æ aSb|ab|¥ë

    ±×¸®°í

        S ¡æ aAb|ab

        A ¡æ aAb|¥ë

    ´Ü, µÎ ¹®¹ý ¸ðµÎ S °¡ ½ÃÀÛ ½Éº¼ÀÌ¶ó °¡Á¤ÇÑ´Ù.

20. ¹®¹ý G = ({S}, {a, b}, S, P) °¡ ´ÙÀ½ »ý¼º±ÔÄ¢À» °®´Â´Ù°í ÇÏÀÚ.

        S ¡æ SS|SSS|aSb|bSa|¥ë

    ÀÌ ¹®¹ýÀÌ ¿¹Á¦ 13 ¿¡¼­ Á¦½ÃµÈ ¹®¹ý°ú µ¿Ä¡ÀÓÀ» º¸¿©¶ó.

21. Áö±Ý±îÁö´Â ¸ðµç »ý¼º±ÔÄ¢µéÀÌ Áº¯¿¡ ÇϳªÀÇ º¯¼ö¸¸À» °®´Â »ó´ëÀûÀ¸·Î °£´ÜÇÑ ¹®¹ýµéÀÇ ¿¹µé¸¸ Á¦½ÃµÇ¾ú´Ù. ¾ÕÀ¸·Î ¿ì¸®°¡ È®ÀÎÇÏ°ÚÁö¸¸, ÀÌ·¯ÇÑ ¹®¹ýµéÀº ¸Å¿ì Áß¿äÇÏ´Ù. ±×·¯³ª Á¤ÀÇ 1 Àº ´õ¿í ÀϹÝÀûÀÎ ÇüÅÂÀÇ »ý¼º±ÔÄ¢µµ Çã¿ëÇÑ´Ù.
´ÙÀ½°ú °°Àº »ý¼º±ÔÄ¢À» °®´Â ¹®¹ý g = ({A, B, C, D, E, S}, {a}, S, P) ¸¦ °í·ÁÇØ º¸ÀÚ.

        S ¡æ ABaC
   Ba ¡æ aaB
   BC ¡æ DC|E
   aD ¡æ Da
   AD ¡æ AB
   aE ¡æ Ea
   AE ¡æ ¥ë

    L(G) ¿¡ ¼ÓÇÏ´Â ¹®ÀåÀ» ¼¼ °³¸¸ À¯µµÇ϶ó. ¶ÇÇÑ À̵é·ÎºÎÅÍ L(G) °¡ ¾î¶² ¾ð¾îÀÎÁö¸¦ ÃßÃøÇØ º¸¾Æ¶ó.

3. ÀÀ¿ë

¿ì¸®°¡ Çü½Ä ¾ð¾î¿Í ¿ÀÅ丶Ÿ¿¡ ´ëÇÑ Ãß»óÀûÀÌ°í ¼öÇÐÀûÀÎ ¸éµé¿¡ ´ëÇØ ¸¹ÀÌ °­Á¶ÇÏ°í ÀÖÁö¸¸ ÀÌ·¯ÇÑ °³³äÀº ÄÄÇ»ÅÍ °úÇÐ ºÐ¾ß¿¡ ³Î¸® ÀÀ¿ëµÇ°í ÀÖÀ¸¸ç, ½ÇÁ¦·Î ¸¹Àº ƯÁ¤ ºÐ¾ßµéÀ» ¿¬°áÇÏ´Â °øÅë ÁÖÁ¦ÀÌ´Ù. º» Àý¿¡¼­´Â µ¶ÀÚµéÀÌ ÀÌ Ã¥¿¡¼­ °øºÎÇÏ´Â ³»¿ëÀÌ ´Ü¼øÈ÷ Ãß»óÈ­ (abstraction) µéÀ» ¸ð¾Æ ³õÀº °Í¸¸ÀÌ ¾Æ´Ï¶ó, ¸¹Àº Áß¿äÇÑ ½Ç¼¼°èÀÇ ¹®Á¦µé¿¡ ´ëÇÑ ÀÌÇØ¿¡ µµ¿òÀ» Áشٴ Ȯ½ÅÀ» ÁÖ±â À§ÇÏ¿©, ¸î °¡Áö °£´ÜÇÑ ¿¹Á¦µéÀ» ¼Ò°³ÇÏ°íÀÚ ÇÑ´Ù.

Çü½Ä ¾ð¾î¿Í ¹®¹ýÀº ÇÁ·Î±×·¡¹Ö ¾ð¾î¿Í °ü·ÃÇؼ­ ³Î¸® »ç¿ëµÈ´Ù. ÇÁ·Î±×·¡¹ÖÀ» ÇÏ´Â °úÁ¤¿¡¼­, ¿ì¸®´Â ´ëºÎºÐÀÇ °æ¿ì »ç¿ëÇÏ´Â ¾ð¾î¿¡ ´ëÇØ ´Ù¼Ò Á÷°üÀûÀÎ ÀÌÇظ¸À» ¹ÙÅÁÀ¸·Î ÀÛ¾÷ÇÏ°í ÀÖ´Ù. ¶§¶§·Î, »ç¿ëÇÏ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾î¿¡ ´ëÇØ Àͼ÷ÇÏÁö ¾ÊÀº ±â´ÉÀ» »ç¿ëÇÏ°íÀÚ ÇÒ ¶§¿¡´Â, ´ëºÎºÐÀÇ ÇÁ·Î±×·¡¹Ö °ü·Ã ¼­Àû¿¡¼­ ãÀ» ¼ö ÀÖ´Â ÇØ´ç ±â´É¿¡ ´ëÇÑ ±¸¹® ´ÙÀ̾î±×·¥ (syntax diagram) µî°ú °°Àº ÀÚ¼¼ÇÑ ¼³¸íÀ» ÂüÁ¶ÇÏ°Ô µÈ´Ù. ÄÄÆÄÀÏ·¯¸¦ °³¹ßÇÒ ¶§³ª ÇÁ·Î±×·¥ÀÇ Á¤È®¼º Áõ¸íÀ» ½ÃµµÇÒ ¶§¿¡µµ, °ÅÀÇ ¸Å ´Ü°è¸¶´Ù ±× ¾ð¾î¿¡ ´ëÇÑ ÀÚ¼¼ÇÑ ¼³¸íÀÌ ÇÊ¿äÇÏ°Ô µÇ´Â °ÍÀÌ´Ù. ÇÁ·Î±×·¡¹Ö ¾ð¾î¸¦ Á¤È®ÇÏ°Ô Á¤ÀÇÇÏ´Â ¹æ¹ý °¡¿îµ¥, ¾Æ¸¶µµ ¹®¹ýÀÌ °¡Àå ³Î¸® »ç¿ëµÈ´Ù.

Pascal À̳ª C ¿Í °°Àº ´ëÇ¥ÀûÀÎ ÇÁ·Î±×·¡¹Ö ¾ð¾î¸¦ ¹¦»çÇÏ´Â ¹®¹ýÀº ¸Å¿ì º¹ÀâÇÏ°í ±Ô¸ð°¡ Å©´Ù. ¿©±â¼­´Â °£´ÜÇÑ ¿¹¸¦ µé±â À§ÇÏ¿© ÀÌ·¸°Ô ±Ô¸ð°¡ Å« ¾ð¾îÀÇ ÀϺκÐÀÎ º¸´Ù ÀÛÀº ¾ð¾î¸¦ °í·ÁÇØ º¸ÀÚ.

±×¸² 4

ÁÖ¾îÁø ÇÁ·Î±×·¥À» ÇÑ ¾ð¾î·ÎºÎÅÍ ´Ù¸¥ ¾ð¾î·Î º¯È¯ÇÏ´Â ÄÄÆÄÀÏ·¯³ª ´Ù¸¥ ¹ø¿ª±â (translator) µéÀº À§¿Í °°Àº ¿¹Á¦¿¡¼­ ´Ù·é ¾ÆÀ̵ð¾îµéÀ» ³Î¸® »ç¿ëÇÑ´Ù. ¿¹Á¦ 15 ¿¡¼­Ã³·³ ÇÁ·Î±×·¡¹Ö ¾ð¾î´Â ¹®¹ýÀ» ÅëÇØ ¸íÈ®È÷ Á¤ÀǵǸç, ¹®¹ý°ú ¿ÀÅ丶Ÿ´Â ÇÁ·Î±×·¥ ÄÚµåÀÇ °¢ ºÎºÐµéÀÌ ÇÁ·Î±×·¡¹Ö ¾ð¾î¿¡¼­ ±ÔÁ¤ÇÑ Á¶°ÇµéÀ» ¸¸Á·Çϸ鼭 ½ÂÀεǴÂÁö¸¦ °áÁ¤ÇÏ´Â µ¥¿¡ ±âº»ÀûÀÎ ¿ªÇÒÀ» ÇÑ´Ù. À§ ¿¹Á¦ 16 Àº ÀÌ·± °áÁ¤ÀÌ ¾î¶»°Ô ÀÌ·ç¾îÁö´ÂÁö¿¡ ´ëÇÑ Ã¹ ÈùÆ®¸¦ ¿¹½ÃÇÑ °ÍÀ̸ç, ÀÌÈÄÀÇ ¿¹Á¦µé¿¡¼­ ÀÌ·± °üÂûÀ» Á»´õ È®ÀåÇÒ °ÍÀÌ´Ù.

¿ÀÅ丶Ÿ¿Í °ü·ÃÇÏ¿© ¶Ç ÇϳªÀÇ Áß¿äÇÑ ÀÀ¿ë ºÐ¾ß´Â µðÁöÅÐ ¼³°è ºÐ¾ßÀ̸ç, ÀÌ ºÐ¾ß¿¡¼­´Â º¯È¯±â°¡ ³Î¸® »ç¿ëµÇ°í ÀÖ´Ù. ÀÌ ºÐ¾ß¿¡ ´ëÇؼ­´Â ÀÌ Ã¥¿¡¼­ ±¤¹üÀ§ÇÏ°Ô ´Ù·çÁö ¾ÊÀ» °ÍÀÌÁö¸¸, ¿©±â¼­ °£´ÜÇÑ ¿¹Á¦¸¦ ¼Ò°³ÇÏ·Á°í ÇÑ´Ù. ¿øÄ¢ÀûÀ¸·Î ¸ðµç µðÁöÅÐ ÄÄÇ»ÅÍ´Â ÇϳªÀÇ ¿ÀÅ丶Ÿ·Î º¼ ¼ö ÀÖÁö¸¸, ±×·¯ÇÑ °üÁ¡ÀÌ ¹Ýµå½Ã ÀûÀýÇÑ °Í¸¸Àº ¾Æ´Ï´Ù. ÄÄÇ»ÅÍÀÇ ÁÖ±â¾ïÀåÄ¡¿Í ³»ºÎ ·¹Áö½ºÅ͵éÀ» ¿ÀÅ丶ŸÀÇ Á¦¾îÀåÄ¡¶ó °¡Á¤ÇØ º¸ÀÚ. ÁÖ±â¾ïÀåÄ¡¿Í ³»ºÎ ·¹Áö½ºÅÍÀÇ ÃÑ ¿ë·®À» n ºñÆ®¶ó ÇßÀ» ¶§ ÀÌ ¿ÀÅ丶Ÿ´Â ¸ðµÎ °³ÀÇ ³»ºÎ »óŸ¦ °®°Ô µÈ´Ù. À̶§ n ÀÇ °ªÀÌ ÀÛ´Ù ÇÏ´õ¶óµµ »óÅÂÀÇ ¼ö´Â ´Ù·ç±â°¡ ºÒ°¡´ÉÇÒ Á¤µµ·Î ±²ÀåÈ÷ Ä¿Áö°Ô µÈ´Ù. ±×·¯³ª ¿ì¸®°¡ ¾ÆÁÖ ´õ ÀÛÀº ´ÜÀ§¸¦ »ìÆ캸¸é, ÀÌ·± °æ¿ì¿¡ ¿ÀÅ丶Ÿ ÀÌ·ÐÀÌ À¯¿ëÇÑ ¼³°è µµ±¸°¡ µÈ´Ù.

±×¸² 6

±×¸² 7

¿¬½À¹®Á¦

1. C ¿¡¼­ÀÇ Á¤¼ö ÁýÇÕ¿¡ ´ëÇÑ ¹®¹ýÀ» Á¦½ÃÇ϶ó.

2. C ¿¡¼­ÀÇ Á¤¼ö¿¡ ´ëÇÑ Àνı⸦ ¼³°èÇ϶ó.

3. C ¿¡¼­ÀÇ ¸ðµç ½Ç¼ö¸¦ »ý¼ºÇÏ´Â ¹®¹ýÀ» Á¦½ÃÇ϶ó.

4. ¾î¶² ÇÁ·Î±×·¡¹Ö ¾ð¾î¿¡¼­, ½Äº°ÀÚ°¡ ¹Ýµå½Ã ¿µ¹®ÀÚ·Î ½ÃÀÛÇØ¾ß ÇÏ°í, Çϳª ÀÌ»ó ¼¼ °³ ÀÌÇÏÀÇ ¼ýÀÚ¸¦ °¡Áú ¼ö ÀÖÀ¸¸ç, ¿µ¹®ÀÚÀÇ °³¼ö¿¡´Â Á¦ÇÑÀÌ ¾ø´Ù°í ÇÏÀÚ. ÀÌ·¯ÇÑ ½Äº°ÀÚµéÀÇ ÁýÇÕÀ» »ý¼ºÇÏ´Â ¹®¹ý°ú Àνı⸦ Á¦½ÃÇ϶ó.

5. Pascal ¿¡¼­ÀÇ var ¼±¾ð¿¡ ´ëÇÑ ¹®¹ýÀ» Á¦½ÃÇ϶ó.

6. ·Î¸¶ ¼ýÀÚ Ç¥±â¹ý (roman number system) ¿¡¼­, ¼ýÀÚµéÀº ¾ËÆĺª {M, D, C, L, X, V, I} ¿¡ ´ëÇÑ ¹®ÀÚ¿­·Î Ç¥ÇöµÈ´Ù. ÀÌµé ¹®ÀÚ¿­ÀÌ ÀûÀýÈ÷ ±¸¼ºµÈ ·Î¸¶ ¼ýÀÚÀÎ °æ¿ì¿¡¸¸ À̸¦ ÀνÄÇÏ´Â Àνı⸦ ¼³°ÔÇ϶ó. ¹®Á¦¸¦ °£´ÜÈ÷ Çϱâ À§ÇÏ¿© ¼ýÀÚ 9 ÀÇ °æ¿ì À̸¦ IX ·Î Ç¥±âÇÏ´Â °Í°ú °°Àº "»©±â" °ü°è ("subtraction" convention) ´ë½Å VIIII ·Î Ç¥±âÇÏ´Â "´õÇϱâ" °ü·Ê ("addition" convention) À» »ç¿ëÇÑ´Ù°í °¡Á¤ÇÏÀÚ.

7. Áö±Ý±îÁö ¿ì¸®´Â ¿ÀÅ丶Ÿ°¡ ÀÌ»ê ½Ã°£ ´ÜÀ§ÀÇ ÇÁ·¹ÀÓ¿öÅ© ±â¹ÝÀ¸·Î µ¿ÀÛÇÔÀ» °¡Á¤ÇÏ¿´Áö¸¸, ÀÌ °üÁ¡Àº ¿ì¸®µéÀÇ ¾ÕÀ¸·ÎÀÇ ³íÀÇ¿¡¼­´Â ±×¸® Å©°Ô ¿µÇâÀ» ÁÖÁö ¾Ê´Â´Ù. ±×·¯³ª µðÁöÅÐ ¼³°è ºÐ¾ß¿¡¼­´Â ½Ã°£À̶ó´Â °³³äÀ» Ưº°ÇÏ°Ô ´Ù·ç¾î¾ß ÇÑ´Ù.
ÄÄÇ»ÅÍ ½Ã½ºÅÛ¿¡¼­´Â ¼­·Î ´Ù¸¥ ±¸¼º¿ä¼Òµé·ÎºÎÅÍ µµÂøÇÏ´Â ½ÅÈ£ (signal) µéÀ» µ¿±âÈ­Çϱâ À§ÇÏ¿© Áö¿¬ ȸ·Î (delay circuitry) ¸¦ ÇÊ¿ä·Î ÇÑ´Ù. ´ÜÀ§-Áö¿¬ º¯È¯±â (unit-delay transducer) ¶õ Àڽſ¡°Ô µé¾î¿À´Â ÀÔ·ÂÀ» ÇÑ ´ÜÀ§½Ã°£¸¸Å­ Áö¿¬½ÃÄÑ Ãâ·ÂÇÏ´Â ±â´ÉÀ» ÇÏ´Â º¯È¯±âÀÌ´Ù. Áï, º¯È¯±â´Â ½Ã°£ t ¿¡ ÇϳªÀÇ ½Éº¼ a ¸¦ ÀԷ¹ÞÀ¸¸é À̸¦ ½Ã°£ t + 1 ¿¡ Ãâ·ÂÇÑ´Ù. ½Ã°£ t = 0 ¿¡´Â, º¯È¯±â´Â ¾Æ¹« °Íµµ Ãâ·ÂÇÏÁö ¾Ê´Â´Ù. °á±¹, º¯È¯±â´Â ÀÔ·Â ¹®ÀÚ¿­ À» Ãâ·Â ¹®ÀÚ¿­ ·Î º¯È¯ÇÏ´Â °ÍÀÌ´Ù.
¾ËÆĺªÀÌ ¥Ò = {a, b} ÀÎ °æ¿ì, ´ÜÀ§-Áö¿¬ º¯È¯±â°¡ ¾î¶»°Ô ¼³°èµÇ¾î¾ß ÇÏ´ÂÁö¸¦ º¸¿©ÁÖ´Â ±×·¡ÇÁ¸¦ ±×·Á¶ó.

8. Àڽſ¡°Ô ÀԷµǴ ¹®ÀÚ¿­À» n-´ÜÀ§ ½Ã°£¸¸Å­ Áö¿¬½ÃÄÑ Ãâ·ÂÇÏ´Â º¯È¯±â¸¦ n-´ÜÀ§ Áö¿¬ º¯È¯±â (n-unit delay transducer) ¶ó ÇÑ´Ù. Áï, ÀÌ º¯È¯±â¿¡´Â ÀÔ·Â ¹®ÀÚ¿­ À» Ãâ·Â ¹®ÀÚ¿­ ·Î º¯È¯ÇÏ´Â °ÍÀ̸ç, ÀÌ º¯È¯±â´Â óÀ½ n ´ÜÀ§ ½Ã°£ µ¿¾ÈÀº Ãâ·ÂÀ» »ý¼ºÇÏÁö ¾Ê´Â´Ù.

        (a) ¾ËÆĺª ¥Ò = {a, b} ¿¡ ´ëÇÑ 2-´ÜÀ§ Áö¿¬ º¯È¯±â¸¦ ±¸¼ºÇ϶ó.

        (b) n-´ÜÀ§ Áö¿¬ º¯È¯±â°¡ Àû¾îµµ °³ÀÇ »óŸ¦ °¡ÁüÀ» º¸¿©¶ó.

9. ¾çÀÇ Á¤¼ö¸¦ Ç¥ÇöÇÏ´Â ÀÌÁø ¹®ÀÚ¿­¿¡ ´ëÇÑ 2 ÀÇ º¸¼ö (2's complement) ´Â ¿ì¼± °¢ ºñÆ®µéÀ» ¸ðµÎ º¸¼ö·Î ¹Ù²Ù°í, ´ÙÀ½À¸·Î ÀÌÀÇ ÃÖÇÏÀ§ ºñÆ®¿¡ 1 À» ´õÇÏ¿© ¾ò¾îÁø´Ù. ÁÖ¾îÁø ÀÌÁø ¹®ÀÚ¿­À» 2 ÀÇ º¸¼ö·Î º¯È¯ÇÏ´Â º¯È¯±â¸¦ ¼³°èÇ϶ó. ÀÌÁø¼ö°¡ ¿¹Á¦ 17 ¿¡¼­¿Í °°ÀÌ Ç¥ÇöµÈ´Ù°í °¡Á¤ÇÑ´Ù. Áï ÇÏÀ§ ºñÆ®°¡ ¹®ÀÚ¿­ÀÇ ¿ÞÂÊ¿¡ ÀÖ´Ù.

10. ÀÌÁø¼ö¸¦ ÆÈÁø¼ö (octal) ·Î ¹Ù²Ù´Â º¯È¯±â¸¦ ¼³°èÇ϶ó. ¿¹¸¦ µé¾î, ÀÌÁø ¹®ÀÚ¿­ 001101110 ¿¡ ´ëÇÏ¿© 156 ÀÌ Ãâ·ÂµÇ¾î¾ß ÇÑ´Ù.

11. ÀÌ ÀÔ·Â ºñÆ® ¹®ÀÚ¿­ÀÌ¶ó °¡Á¤ÇÏÀÚ. ÀÌ ÀÔ·Â ¹®ÀÚ¿­ÀÇ ¸ðµç 3-ºñÆ® ºÎ¹®ÀÚ¿­ (substring) ÀÇ Æи®Æ¼ (parity) ¸¦ °è»êÇÏ´Â º¯È¯±â¸¦ ¼³°èÇ϶ó. ÀÌ º¯È¯±â´Â ´ÙÀ½°ú °°Àº Ãâ·ÂÀ» »ý¼ºÇÏ¿©¾ß ÇÑ´Ù.

    ¿¹¸¦ µé¾î, ÀÔ·Â 110111 ¿¡ ´ëÇؼ­´Â Ãâ·Â 000001 À» »ý¼ºÇÏ¿©¾ß ÇÑ´Ù.

12. ºñÆ® ¹®ÀÚ¿­ À» ÀÔ·ÂÀ¸·Î ¹Þ¾Æ, ¸Å ¼¼ °³ÀÇ ¿¬¼ÓµÈ ºñÆ®·Î ÀÌ·ç¾îÁø ÀÌÁø Á¤¼ö¸¦ ¹ý 5 (modulo 5) ¿¡ ´ëÇÏ¿© °è»êÇÏ´Â º¯È¯±â¸¦ ¼³°èÇ϶ó. Áï, ÀÌ º¯È¯±â´Â ´ÙÀ½À» ¸¸Á·ÇÏ´Â Ãâ·Â À» »ý¼ºÇÏ¿©¾ß ÇÑ´Ù.

13. ÀϹÝÀûÀ¸·Î µðÁöÅÐ ÄÄÇ»ÅÍ´Â ¸ðµç Á¤º¸¸¦, ƯÁ¤ ÇüÅÂÀÇ ÀÎÄÚµù ±â¹ýÀ» »ç¿ëÇÏ¿©, ºñÆ® ¹®ÀÚ¿­·Î Ç¥ÇöÇÑ´Ù. ¿¹¸¦ µé¾î, ¹®ÀÚ Á¤º¸´Â Àß ¾Ë·ÁÁø ASCII Äڵ带 »ç¿ëÇÏ¿© ÀÎÄÚµùµÉ ¼ö ÀÖ´Ù.
µÎ °³ÀÇ ¾ËÆĺª {a, b, c, d} ¿Í {0, 1} ¿¡ ´ëÇÏ¿© ´ÙÀ½°ú °°ÀÌ Á¤ÀÇµÈ Ã¹ ¹ø° ¾ËÆĺªÀ¸·ÎºÎÅÍ µÎ ¹ø° ¾ËÆĺªÀ¸·ÎÀÇ ÀÎÄÚµùÀ» °í·ÁÇØ º¸ÀÚ.

     ¾ËÆĺª {0, 1} ¿¡ ´ëÇÑ ¹®ÀÚ¿­À» ¿ø·¡ ¸Þ½ÃÁö·Î Çص¶ (decode) ÇÏ´Â º¯È¯±â¸¦ ±¸¼ºÇØ º¸¶ó. ¿¹¸¦ µé¾î, ÀÔ·Â 010011 Àº Ãâ·Â bad ·Î º¯È¯µÇ¾î¾ß ÇÑ´Ù.

14. µÎ °³ÀÇ ¾çÀÇ ÀÌÁø¼ö x ¿Í y ¸¦ ÀÔ·Â¹Þ¾Æ Ãâ·ÂÀ¸·Î max (x, y) ¸¦ »ý¼ºÇÏ´Â º¯È¯±â¸¦ ¼³°èÇ϶ó.