چگونه تشخیص می دهیم که زبان زیر مستقل از متن هست؟
این زبان یکی از گزینه های(گزینه ۳) تست کنکور ارشد سال ۸۵ هست.
[tex]L=\left \{ u\, vwv^{R}|u,v,w\in \left \{ a,b \right \}^{ },|u|=|w|=2 \right \}[/tex]
سلام.
ببینید نوشته که طول u,w برابر ۲ باشه، پس u و w میتوانند حالات زیر رو داشته باشند. aa,ab,ba,bb . و همین محدودیت باعث میشه که این دوتا بصورت نامحدود بهم وابسته نیاشند. اما v و معکوس اون به هم وابسته هستند، و میشه گرامر مستقل براش نوشت. اگه محدودیت بر روی طول u,w گذاشته نمیشد، قضیه فرق می کرد.