حل تمرین نظریه محاسبات/فصل اول/حل تمرین ۱-۲۷

حل تمرین ۱-۲۷

تمرین

الفبای Σ_۲ تعریف شده در مساله ۲۶-۱ رادر نظر بگیرید. فرض کنید که هر سطر یک عدد دودویی (باینری) بوده و زبان D به صورت زیر باشد:

{ردیف بالا عددی بزرگتر از ردیف پایین باشد.|^* Σ_۲ متعلق به D={w

به طور مثال (۰و۰) و (۱و۱) و (۰و۱) و (۰و۰) متعلق به این زبان است اما (۱و۰) و (۱و۱) و (۰و۰) متعلق به این زبان نیست. نشان دهید که D منظم است.

حل

اگر بتوان برای زبان خواسته شده، یک DFA رسم کرد، می توان ادعا نمود که زبان مورد نظر منظم است. بدین منظور برای ماشینی کردن زبان، زوج ...(u,v) و (x,y) را به صورت ...xyuv نشان می‌دهیم که x و u واقع در سطر بالا و y و v موجود در سطر پایین است.

با این وصف هر رشته متعلق به زبان D است اگر هر جایگاه زوج از جایگاه فرد قبل از خود کوچکتر یا مساوی باشد. بنابراین اگر در اولین زوج غیر برابر در رشته، (1و0) ظاهر شود، رشته به زبان تعلق نخواهد داشت.

اکنون یک DFA برای زبان رسم می کنیم:

زبان خواسته شده

چون توانستیم برای این زبان یک DFA طراحی کنیم لذا زبانی منظم است.