حل تمرین نظریه زبانها و ماشینها/فصل سوم/حل تمرین بخش ۳-۳

تمرین 1: از آنجایی که زبان فرض شده غیر تهی است پس حتماباید شامل یک حالت شروع و حالت پذیرش باشد که در کمترین حالت هردوی این دو حالت یکی می شوند پس حداقل شامل یک حالت خواهد بود. از طرفی باید با حداقل یک نماد (حتی تهی) در حالت پذیرش بماند پس می توان گفت حتما شامل x<-Y می شود.

تمرین 5:

یک گرامر منظم پیدا کنید که زبان هایی روی ={a,b}∑ که شامل تمام رشته ها با طول حداکثر سه a می باشند را تولید کند. S→bS|aA|ε A→bA|aB| ε B→bB|aC| ε C→bC| ε

تمرین 7: b*U(b*ab*)U(b*ab*ab*)o

تمرین 25: حداقل حالت هایی که نیاز داریم تا یک محیط بسته ایجاد شود 4 حالت است که می توانیم با آن یک مربع بسازیم.