سلام
توی کتاب پوران نوشته مسئله : ماشین M یک LBA و زبان M تهی باشد یک مسئله تصمیم ناپذیر است. و توی یه جدولی نوشته که تهی بودن زبان های حساس به متن تصمیم پذیره .
مگه ماشینی که زبان حساس به متن رو میپذیره LBA نیست پس چرا این دوتا متفاوت هستند؟!
سلام
من متن کتاب ها رو ندیدم
ولی شاید تو کتاب پوران مسئلله ای که نوشته شامل دو زیر مسئله باشه
۱- تشخیص آن که ماشین M یک LBA است
۲- زبان M تهی است
و مسئله ی گفته شده در کتاب پوران ممکنه and این دو عبارت باشه که چون عبارت اول تصمیم ناپذریه پس کلا تصمیم ناپذیر می شه
برای زبانهای حساس به متن، اینکه چک کنی یک زبان تهی هست یا نه، تصمیم ناپذیره. یعنی: "نمیتونی قاطعانه بگی فلان زبان هیچ چیز رو نمیپذیره."
اما مسئله پذیرفتن یک رشته، برای زبانهای حساس به متن، تصمیم پذیره. یعنی: "اگر فلان رشته رو بهت بدن، با استفاده از LBA میتونی قاطعانه بگی این رشته توسط این زبان پذیرفته میشه یا نه"
دقت کن که اینا، ۲ تا مفهوم یا مسئله جدا از همدیگه هستند. اولی میگه آیا L تهی است؟ و دومی میگه آیا رشته W در L عضویت دارد؟