(۲۸ اردیبهشت ۱۳۹۵ ۰۷:۰۶ ب.ظ)ACM نوشته شده توسط: سلام دوستان ممنون میشم به سوالم سریع جواب بدید
اگه زبان L منظم باشه ، چجور ثابت می کنیم که زبان زیر هم منظم هست :
{W|W∈L,WR∈L}
سلام.این زبان جدید شامل رشته هایی است که خودشون و وارونشون عضو زبان L که یک زبان منظم است،هستند.
میتونیم این زبان رو اینجور هم تفسیر کنیم:
W∈L,W∈LR
یعنی رشته هایی که عضو زبان L و عوض وارون زبان L باشند.
پس یعنی رشته هایی که عضو اشتراک
L و
LR هستند. یعنی
ٌW∈L∩LR
پس این زبانی که نوشتید برابر است با
{W:W∈L∩LR}
و با توجه به اینکه زبانهای منظم تحت عملگر وارون(معکوس) بسته اند،پس
LR منظم است.
و چون زبانهای منظم تحت اشتراک متناهی بسته هستند،پس
L∩LR نیز منظم است.
