حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-38

حل تمرین 1-38

تمرین

لم تزریق بیان می کند که هر زبان منظم دارای یک طول تزریق P می باشد که هر رشته ای در زبان که دارای طول حداقل p باشد قابل تزریق است . اگر p طول تزریق برای زبان A باشد آنگاه هر p'>= p نیز یک طول تزریق است . طول تزریق حداقل برای A کوچکترین عدد داده شده است که می تواند طول تزریق A باشد . بطور مثال اگر *A=01 باشد طول تزریق حداقل برابر 2 می باشد.

دلیل این مسئله این است که S=0 عضو A و دارای طول یک بوده ولی قابل تزریق نیست و هر رشته درA باطول 2 یا بیشتر دارای نماد 1 بوده می توان آن را به صورت x=0 و y=1 و z بقیه رشته تقسیم کرده و y را تزریق کرد.

برای هر کدام از زبان های زیر حداقل طول تزریق را به دست آورده و پاسخ خود را توجیه کنید.

الف ) *0001
ب ) *1*0
پ ) *(01)
ت ) 01
ث ) اپسیلون

حل

الف ) حداقل طول تزریق برابر با 4 می باشد علت آن به این صورت است که با فرض x=000 و y=1 و z ادامه رشته تقسیم کرد و y را تزریق کرد.
ب )حداقل طول تزریق برابر با 2 می باشد علت آن به این صورت است که با فرض x=0 و y=0 و z ادامه رشته تقسیم کرد و y را تزریق کرد یا با فرض x=1 و y=0 و z ادامه رشته تقسیم کرد و y را تزریق کرد یا با فرض x=0 و y=1 و z ادامه رشته تقسیم کرد و y را تزریق کرد یا با فرض x=1 و y=1 و z ادامه رشته تقسیم کرد و y را تزریق کرد.
پ ) حداقل طول تزریق برابر با 2 می باشد علت آن به این صورت است که با فرض x مساوی لاندا و y=01 و z ادامه رشته تقسیم کرد و y را تزریق کرد.
ت ) حداقل طول تزریق برابر با 2 می باشد علت آن به این صورت است که در صورت اینکه زبان از یک رشته ثابت تشکیل شده باشد حداقل طول تزریق برابر با طول همان رشته خواهد بود تا همان رشته را بتوان ایجاد کرد و در غیر این صورت نمی توان حداقل طول تزریقی را برای آن در نظر گرفت.
ث ) حداقل طول تزریق برابر با 1 می باشد علت آن به این صورت است که در صورت اینکه زبان از یک رشته ثابت تشکیل شده باشد حداقل طول تزریق برابر با طول همان رشته خواهد بود تا همان رشته را در برگیرد و در غیر اینصورت نمی توان حداقل طول تزریقی را برای آن در نظر گرفت.