*پذیرنده زبانها (ماشین پذیرنده زبان )AUTAMATA
معماری پذیرنده زبان نوع سوم:همیشه ورودی پذیرنده یک رشته می باشد ،ماشین نوع سوم یک نوار نیمه متناهی دارد و یک کنترل متناهی و یک هد فقط خواندنی داریم
کنترل متناهی در هر حالت وضعیت ماشین را به ما نشان می دهد.
چگونه با ماشین برخورد می کنیم:
1)رشته را روی نوار قرار می دهیم.
2)ماشین را در وضعیت اولیه می گذاریم تا ماشین شروع به پردازش نماید.
3)پس از اینکه ماشین شروع به کار کرد در انتهای رشته وضعیت ماشین بررسی می شود که ایا در وضعیت
نهایی قرار دارد یا نه؟!
*پذیرش:زمانی اتفاق میافتد که در انتهای رشته ماشین در یکی از حالات نهایی خود باشد. Accep
*عدم پذیرش:زمانی اتفاق می افتد که در انتهای رشته ماشین در یکی از حالات غیر نهایی خود باشد و یا اینکه ماشین به دلایلی نامعلوم متوقف شود Regict
آیتم های ماشین نوع سوم:
M:(مجموعه حالات , Qالفبای زبان ,∑تابع انتقال , δ حالت اولیه , qمجموعه حالات نهاییf )
{همیشه یک نقطه شروع داریم ولی می توانیم چندین نقطه پایان داشته باشیم}
*تعریف تابع انتقال :
Q×∑→Q : δ
Q =(Q,∑)δ
طریقه خواندن بر حسب نوار است:
b a b b a
q0→q0→q1→q1→q0→q1
*رشته ی abbab توسط ماشین فوق پذیرفته شد (accept)
*مثالی دیگر
:
a b b a
0→q0→q1→q1→q0 q
چون به حالت نهایی نرسیده است می شود reject))
*تابع انتقال دو حالت دارد:1)گراف انتقال 2)جدول انتقال