ماشین حالات متناهی
ماشینهای حالات متناهی (Finite state machines) اختصاراً FA، به مدلهایی مجرد[۱] از ماشینها [۲] اطلاق میگردد که قادرند در مجموعهای متناهی از حالات[۳] وجود داشته باشند.
یک ماشین حالت متناهی، یک ابزار ریاضی برای توصیف پردازش توسط یک ماشین است. یک FA میتواند در یکی از تعداد متناهی حالات مفروض باشد و با دریافت هر ورودی بین این حالات حرکت کند. به بیان بهتر از حالتی به حالت دیگر با توجه به اندازه یا نوع ورودی (مثلا مقدار ۰ یا ۱ یا علامت مثبت یا منفی) منتقل شود. بعد از حالت اولیه (استارت استیت) نماد ورودی خوانده میشود، تعدادی عمل محاسباتی با توجه به همان نماد خوانده شده انجام شده، نمادی خارج کرده (تولید) و به حالتی دیگر با توجه به نماد ورودی جدید، منتقل میشود. در این حال اگر FA در حالتی ورودیای بگیرد و در آن حالت مسیر حرکت برای نماد ورودی تعیین نشده باشد، اصطلاحا ماشین گیر خواهد کرد.[۴]
محتویات |
موارد کاربرد [ویرایش]
ماشینهای حالات متناهی را به وفور در کاربردهای وابسته به علوم کامپیوتر و شبکهٔ دادهها مورد استفاده قرار میدهند[۵] همین طور ماشینهای حالات متناهی می توانند تعداد زیادی از مسئله ها را مدلسازی کنند که در بین آن ها می توان به ماشین طراحی الکترونیکی ، طراحی پروتکل ارتباطات ، تجزیه گر زبان و دیگر کاربردهای مهندسی نام برد.در تحقیقات زیست شناسی و هوش مصنوعی ، ماشین های حالت یا ماشین های حالت سلسله مراتبی برای توصیف دستگاه عصبی و در زبان شناسی به منظور توصیف گرامرهای زبان های طبیعی استفاده می شوند .
از لحاظ یک مدل محاسباتی انتزاعی ، ماشینهای حالات متناهی نسبت به دیگر مدل های محاسباتی نظیر ماشین تورینگ قدرت محاسباتی کمتری دارند.[۶]به این معنا که کارهایی هست که FSM نمی تواند انجام دهد اما ماشین تورینگ می تواند. این به خاطر این است که FSM حافظه محدود دارد. حافظه محدود به تعداد حالات متناهی شده است.[۷]
پانوشتهها [ویرایش]
- ↑ Abstract
- ↑ Automaton
- ↑ States
- ↑ http://www.davidsalomon.name/DC2advertis/AppendF.pdf
- ↑ ریاضیات گسسته و کاربردهای آن، ص. ۷۹۶
- ↑ ^ Belzer, Jack; Albert George Holzman, Allen Kent (1975). Encyclopedia of Computer Science and Technology, Vol. 25. USA: CRC Press. pp. 73. ISBN 0824722752.
- ↑ http://en.wikipedia.org/wiki/Finite_state_machine
جستارهای وابسته [ویرایش]
منابع [ویرایش]
- ریاضیات گسسته و کاربردهای آن (انگلیسی)
- Jackson, Jr., Philip C., Introduction to Artificial Intelligence, ۲nd enlarged and slightly corrected ed., Dover Publications, Inc., New York, 1985. ISBN 0-486-24864-X
پیوندهای بیرونی [ویرایش]
 |
در ویکیانبار پروندههایی دربارهٔ ماشین حالات متناهی موجود است. |
