حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۱۳
زبان G شامل رشته هایی میباشد که یا • یک # • دو # • 0k#0i#0j
و یا i تا صفر و # و 2i تا صفر دیگر
قسمت ب:
برای اثبات اینکه زبان مورد نظر منظم نیست از لم تزریق استفاده میکنیم. رشته ی 00..0#0000..0 را در نظر میگیرم که علامت # P امین نماد ورودی میباشد. فرض میکنیم زبان مورد نظر منظم است پس لم تزریق در آن برقرار است. y را یکبار شامل # و یک بار # به تنهایی در نظر میگیریم. اگر Y را مثلا سه بار تزریق کنیم تعداد # ها با رشته های قابل پذیرش زبان مطابقت نمیکند. پس زبان منظم نیست.
شهره دلداری