تالار گفتمان مانشت

سلام

محدودیتی برای تبدیل مستقل از متن به نرمال چامسکی هست؟

قضیه 6.6 کتاب لینز
هر گرامر مستقل از متن G که [tex]\lambda\notin L(G)[/tex]گرامرمعادلی در فرم نرمال چامسکی دارد.

(19 آبان 1393 09:26 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ]قضیه ۶/۶ کتاب لینز
هر گرامر مستقل از متن G که [tex]\lambda\notin L(G)[/tex]گرامرمعادلی در فرم نرمال چامسکی دارد.

ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟

(19 آبان 1393 10:02 ب.ظ)Imankhani نوشته شده توسط: [ -> ]

(19 آبان 1393 09:26 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ]قضیه ۶/۶ کتاب لینز
هر گرامر مستقل از متن G که [tex]\lambda\notin L(G)[/tex]گرامرمعادلی در فرم نرمال چامسکی دارد.

ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟

هر فرم گرامری برای هدفی مطرح شده ؛ وجود یا عدم وجود لامبدا قدرت فرم خاصی رو افزایش نمیده می تونید در تعریف زبان اگر لامبدا جز زبان بود اجتماع بگیرید.

(19 آبان 1393 10:02 ب.ظ)Imankhani نوشته شده توسط: [ -> ]ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟

در نرمال چامسکی سمت چپ یک عبارت از گرامر نمیتونه رشته بطول 0 باشه. برای همین فرم نرمال رو برای زبان زیر مینویسن:

[tex]L1=L-\{\lambda\}[/tex]

ممنون و متشکر.