دوستان میشه بفرمایید که زبان های زیر کدومشون مستقل از متن و کدوم وابسته به متن هستند؟
۱- {a^n b^2n c^m | n>=0 , m>=0}
۲-{a^2n b^n c^m | n>=0 , m>=0}
۳- {a^n a^m c^2m | n>=0 , m>=0}
ممنونم ازتون...
هر سه مستقل از متن هستش
۱- برای طراحی pda آن کافیست به ازای هر a ای که در ورودی می بینیم دوتا a در پشته push کنیم و وقتی به b ها رسیدیم به ازای هر b یک a را از پسته pop کنیم این طوری هر a را با دو b تطبیق می دهیم و بعد هر چه c می بینیم رد می کنیم.
۲- برای طراحی pda آن کافی است به ازای هر دوa ای که می بینیم یک a در پشته push کنیم سپس به ازای هر b که در ورودی می بینیم یک a از پشته pop کنیم در این صورت هر دو a را با یک b تطبیق داده ایم بعد هر چه c می بینیم رد می کنیم
۳- رشته های زبا سوم بدین صورتند که در ابتدا یک سری a داریم و بعد یک سری c و تنها شرطی که باید داشته باشد این است که تعداد c ها باید زوج باشد پس منظم است و dfa آن به صورت زیر است.
![[تصویر: 276778_dfa3.jpg]](https://img.manesht.ir/276778_dfa3.jpg)
زبان سوم منظم نیست و مستقل از متن است. مثلا رشته [tex]aac^{100}[/tex] عضو زبان سوم نمی باشد ولی عضو زبان ماشین طراحی شده در پاسخ شما می باشد.
در واقع به نظرم تعداد c ها در زبان سوم هر عدد زوجی هست که نصفش کمتر یا مساوی تعداد a ها باشه. پس نیاز است ماشین ما تعداد a ها رو به یاد داشته باشه و چون محدودیتی روی تعداد a ها نداریم، این کار نیاز به حافظه نا متناهی داره پس زبانش منظم نیست.
(۰۲ خرداد ۱۳۹۳ ۰۷:۳۷ ق.ظ)Morris نوشته شده توسط: زبان سوم منظم نیست و مستقل از متن است. مثلا رشته [tex]aac^{100}[/tex] عضو زبان سوم نمی باشد ولی عضو زبان ماشین طراحی شده در پاسخ شما می باشد.
بله کاملا حق با شماست
ممنون