حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-32
حل تمرین1-32
تمرین: رشته x را پیشوند رشته y گویند اگر رشته ای مانند z موجود بوده که xy=z باشد. X را پیشوند سره برای y گویند اگر که شرط xy رانیز داشته باشد. در هرکدام از قسمتهای زیر عملیاتی روی زبان A تعریف می شود. نشان دهید که زبان های منظم تحت عملیات زیر بسته اند. الف) { هیچ پیشوند سره از w عضو A نباشد | wA } = NOPREFIX(A) ب) {w پیشوند سره هیچ رشته ای در A نباشد | wA } = NOEXTENDED(A)
حل:
(aابتدا زبان L1 را به صورت زیر در نظر میگیریم: { رشته هایی مانند y در A که پیشوند سره برای w هستند : w } =1L وسپس _1, q_1 〖,F〗_1) NFA N=(Q_1,,را می سازیم که L1 را بر طبق موارد زیر می شناسد : Q_1=Q{q_f} که در آن : q_fQ (حالت جدیدی که تعریف کردیم) _1 : بر طبق زیر برای هر 〖qQ〗_1 و هر {}تعریف شده است : _1(q, ) = {(q, )} if qQ-F &
{(q, )} {q_f} if q F &
{q_f} if q{q_f} &
otherwise
q0=q1 〖F1={q〗_f}
N ، L1 را می شناسد زیرا : اگر w رشته ای در L1 باشد ، رشته ای مانند y وجود دارد در A که پیشوند سره ای برای w است ، یا w=xy ، که درآن x تهی نیست. اگر w به عنوان یک ورودی N با شد .برخی اعمال روی y حالت پایان را حالت پذیرشی در M قرار می دهد. اگر w رشته پذیرفته شده ای به وسیله N باشد ، برخی اعمال جود دارند که در q_fپایان می پذیرد اگر W به عنوان ورودی N باشد این اعمال باید به یکی از حالات پذیرش درM قبل از اینکه درq_f تمام شود برسد. پیشوند سره w که برای قسمتی از اعمال استفاده می شود y است و می توان مشاهده کرد که اگر y ورودیM باشد در یکی از حالات پذیرش آن خط می شود که معنای آن را می دهد کهy در A وجود دارد وw رشته ای در L_1می باشد. پس واضح است که NOPREFIX(A)=A~ L1 که این زبا ن منظم تحت عملیات ذکر شده بسته است .
(b { w پیشوند سره برخی رشته ها مانندy در A است : w } =1L و _1, q_1 〖,F〗_1) DFA N=(Q_1,, را میسازیم که L1 را بر طبق موارد زیر می شناسد : Q1=Q 1= q0=q F1={qQ : F-{q}} به نحوی که q در مسیر q_0 تا p است. به نحوی که Q در مسیر q0 تا P قرار دارد. M1،L1 را می شناسد زیرا : - اگر w رشته ای ازL1 باشد ،پیشوند سره ای از y درA وجود دارد. اگر M ،y را به عنوان ورودی بپذیرد،در یکی از حالات پذیرش حالت p تمام می شود . بنابر این اگر M1؛w را به عنوان ورودی بپذیرد در یکی از حالات مسیر از q0 تاp پایان می پذیرد که معنای آن را دارد که w در یکی از حالات پذیرش اگر به عنوان ورودیM1 باشد تمام می شود - اگر w به وسیله M1 پذیرفته شود در یکی از حالات پذیرش تمام می شود ، این معنای آن را می دهد که در حالتی درM روی مسیری ازq0 تا یکی از حالات پذیرش M است تمام می شود.بنابر اینw پیشوندی سره ای از رشته ی y در A است و در زبان L1 قرار دارد.