تالار گفتمان مانشت
محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - نسخه‌ی قابل چاپ

محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - Imankhani - 19 آبان ۱۳۹۳ ۰۶:۴۸ ب.ظ

سلام

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

RE: محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - fatemeh69 - 19 آبان ۱۳۹۳ ۰۹:۲۶ ب.ظ

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

RE: محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - Imankhani - 19 آبان ۱۳۹۳ ۱۰:۰۲ ب.ظ

(۱۹ آبان ۱۳۹۳ ۰۹:۲۶ ب.ظ)fatemeh69 نوشته شده توسط:  قضیه ۶/۶ کتاب لینز
هر گرامر مستقل از متن G که [tex]\lambda\notin L(G)[/tex]گرامرمعادلی در فرم نرمال چامسکی دارد.
ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟

RE: محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - Pakniat - 19 آبان ۱۳۹۳ ۱۱:۳۷ ب.ظ

(۱۹ آبان ۱۳۹۳ ۱۰:۰۲ ب.ظ)Imankhani نوشته شده توسط:  
(19 آبان ۱۳۹۳ ۰۹:۲۶ ب.ظ)fatemeh69 نوشته شده توسط:  قضیه ۶/۶ کتاب لینز
هر گرامر مستقل از متن G که [tex]\lambda\notin L(G)[/tex]گرامرمعادلی در فرم نرمال چامسکی دارد.
ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟
هر فرم گرامری برای هدفی مطرح شده ؛ وجود یا عدم وجود لامبدا قدرت فرم خاصی رو افزایش نمیده می تونید در تعریف زبان اگر لامبدا جز زبان بود اجتماع بگیرید.

RE: محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - Jooybari - 20 آبان ۱۳۹۳ ۱۲:۳۶ ق.ظ

(۱۹ آبان ۱۳۹۳ ۱۰:۰۲ ب.ظ)Imankhani نوشته شده توسط:  ممنون از جوابتون دلیل اینکه لاندا تو زبون نباید باشه چیه؟ چرا فرمای نرمال لاندا رو فبول نمیکنن؟

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

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

RE: محدودیت برای تبدیل مستقل از متن به نرمال چامسکی - Imankhani - 21 آبان ۱۳۹۳ ۱۱:۰۶ ق.ظ

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