شنبه ٠٤ آذر ١٣٩٦
رشته های پایه
مقدمه ای بر نظریه زبان ها و محاسبات

قیمت : 300,000  ریال

مقدمه ای بر نظریه زبان ها و محاسبات
مهندس فاطمه هل اتائی- مهندس مارال صالحی

 

 

امروزه کامپیوترها نقش و جایگاه مهمی در زندگی انسانها دارند، به طوری که بیان منطقی "نظریه محاسبات[1]"، به عنوان پروژه‌ای بزرگ مطرح می‌باشد. رویکرد مطرح در اینجا با وجود ساده و قدیمی بودن، همچنان امکان تفکر قاعده مند در مورد نحوه عملکرد کامپیوترها را فراهم میسازد. این رویکرد به این صورت است که کامپیوتر، ورودی‌ها را به صورت رشته‌ای از کاراکترها دریافت می‌کند، روی آن‌ها محاسباتی انجام می‌دهد و خروجی‌هایی تولید می‌نماید.

 

 

 

 

در بخش اول این کتاب، مفهوم کامپیوترها حتی ساده تر از این بیان شده است، زیرا این کامپیوترها به سؤالاتی که از آن‌ها پرسیده می‌شود فقط می‌توانند با بله یا خیر پاسخ ‌دهند. برای مثال رشته‌ای را به عنوان ورودی فرستاده و می‌پرسیم، "آیا این رشته یک عبارت جبری مجاز است؟". در اینجا کامپیوتر به عنوان "پذیرنده زبان[2]" عمل می‌کند. زبان پذیرفته شده شامل مجموعه رشته‌هایی است که پاسخ کامپیوتر برای آن‌ها "بله" باشد. در این مثال، زبان پذیرفته شده شامل عبارت‌های جبری مجاز می‌باشد. پذیرفتن یک زبان تقریباً مشابه حل یک "مسأله تصمیم‌گیری[3]" است، به این صورت که کامپیوتر، رشته‌ای را به عنوان "نمونه‌ای" از مسأله دریافت کرده و به شکل بله یا خیر پاسخ می‌دهد. بسیاری از مسائل محاسباتی جالب را می‌توان به صورت مسائل تصمیم گیری در آورد، و پس از دستیابی به مدل‌های محاسباتی با توانایی تولید پاسخ‌هایی پیچیده‌تر از بله یا خیر، همچنان می‌توان آنها را به عنوان مسائل تصمیم گیری، مورد مطالعه قرار داد.

اگر خود را در لحظه محدود کنیم، آنگاه به منظور انجام محاسبات لازم برای حل مسائل تصمیم گیری و نیز برای پذیرفتن زبان‌ها، می‌توان سطح پیچیدگی مدل خود را به یکی از دو روش زیر تنظیم کرد. روش اول عبارتست از تغییر مسائلی که سعی در حل آن‌ها داریم یا تغییر زبانهایی که سعی در پذیرفتن آنها داریم، و نیز ارائه مدلی مناسب برای این سطح از مسأله. پذیرش زبانی شامل عبارت‌های جبری مجاز، مسأله نسبتاً مشکلی است و با استفاده از اولین مدل محاسباتی بیان شده نمی تواند پذیرفته شود، اما به زودی در این کتاب به آن پرداخته خواهد شد. روش دوم عبارتست از توجه به خود محاسبات؛ به این صورت که در ابتدا بررسی شود پیچیدگی مراحلی که توسط کامپیوتر انجام می‌شود تا چه میزان مجاز است، و اینکه چه گونه ای از زبان‌ها به عنوان نتیجه می‌تواند مورد پذیرش قرار بگیرد. مدل اول ما یک ماشین متناهی[4] است که با نقطه ضعفش که همان نداشتن حافظه کمکی است شناخته می‌شود، و زبان پذیرفته شده توسط چنین ماشینی نمی تواند به پذیرنده ای نیاز داشته باشد که در طول محاسبات خود اطلاعات بسیار زیادی را به یاد بیاورد.

ماشین متناهی، در پاسخ به نمادهای ورودی، با حرکت در میان تعداد متناهی از حالت‌های متمایز، به پیش می‌رود. هروقت به یک حالت پذیرش[5] برسد، در پاسخ به رشته‌ای از نمادهای ورودی که تاکنون دریافت کرده است "بله" می‌گوید. زبان‌هایی که می توانند توسط ماشینی متناهی پذیرفته ‌شوند، زبان منظم[6] هستند. این زبان‌ها را می‌توان با استفاده از "عبارت‌های منظم[7]" و یا "گرامرهای منظم[8]" توصیف نمود و می‌توان با ترکیب زبان‌های تک عضوی و به کارگیری بعضی عملگرهای ساده، آن‌ها را تولید کرد. دسته دیگری از ماشین‌های متناهی که در سطح بالاتری قرار می‌گیرد، "ماشین پشته‌ای[9]" می‌باشد. زبان‌هایی که توسط ماشین‌های پشته‌ای پذیرفته می‌شوند، می‌توانند توسط گرامر جامع‌تری به نام "گرامرهای مستقل از متن[10]" تولید شوند. گرامرهای مستقل از متن قادر هستند اکثر نحوه نگارش[11] زبان‌های برنامه‌نویسی سطح بالا و همچنین زبانهای مرتبطی مانند عبارت‌های جبری مجاز و رشته پرانتزهای متوازن، را توصیف کنند. جامع‌ترین مدل محاسباتی که بیان خواهد شد، ماشین تورینگ[12] است که در اصل می‌تواند هر گونه روند الگوریتمی را اجرا کند. این ماشین به اندازه کامپیوتر توانمند است. ماشین‌های تورینگ زبان‌های بازگشتی برشمارا[13] را می‌پذیرند و یک روش برای تولید این زبان ها استفاده از گرامرهای نامحدود[14] می‌باشد



[1]Theory of computation

[2]Language acceptor

[3] Decision problem

[4] Finite automaton

[5] Accepting state

[6] regular languages

[7] regular expressions

[8] regular grammars

[9] Pushdown automaton

[10] Context-free grammar

[11] Syntax

[12] Turing machine

[13] Recursively Enumerable language

[14] Unrestricted grammars

اوقات شرعی
آمار بازدید
 بازدید این صفحه : 47383
 بازدید امروز : 84
 کل بازدید : 491209
 بازدیدکنندگان آنلاين : 5
 زمان بازدید : 0/2344
تقویم
Copyright  © 2014 press.semnan.ac.ir.semnan.ac.ir . All rights reserved