زمان کنونی: ۲۴ آذر ۱۳۹۷, ۱۱:۳۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

زبان تهی ومکمل آن

ارسال:
  

Msccom پرسیده:

زبان تهی ومکمل آن

آیا زبان تهی مکمل سیگما استار هست؟
آیا زبان ال منهای سیگما استار برابر با تهی است؟
چرا؟
تعریف تفاضل دو زبان به صورت اشتراک زبان اول با مکمل زبان دوم نیست مگه؟
آیا عبارت زیر فقط برای زبانهای منظم تعریف میشه؟
مکمل زبان ال=سیگما استار منهای ال

۰
ارسال:
  

mfXpert پاسخ داده:

زبان تهی ومکمل آن

(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  آیا زبان تهی مکمل سیگما استار هست؟
بله
(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  آیا زبان ال منهای سیگما استار برابر با تهی است؟
بله
(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  آیا عبارت زیر فقط برای زبانهای منظم تعریف میشه؟
مکمل زبان ال=سیگما استار منهای ال
نه.این تعریف برای هر زبانی صدق می کنه

۰
ارسال:
  

sasanlive پاسخ داده:

RE: زبان تهی ومکمل آن

(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  آیا زبان تهی مکمل سیگما استار هست؟
آیا زبان ال منهای سیگما استار برابر با تهی است؟
چرا؟

ماشینه سیگما استار تنها یه حالت q0 هست که با تمام الفبا به خودش میره و همچنین گره پایانی نیز هست.
برای مکمل کردن dfa تمام حالات پایانی رو به حالت غیر پایانی تبدیل میکنیم. دراینجا تنها یه حالت داریم که حالت q0 هست که اونو به شکل غیر پایانی در میاریم پس ماشین به هیچ حالت پایانی نمیره و هیچ الفبایی رو نمی پذیره. که همون تهی میشه.
ضمنا در ماشینها و گرامرها لاندا تهی نیست اشتباه نگیرین.

(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  تعریف تفاضل دو زبان به صورت اشتراک زبان اول با مکمل زبان دوم نیست مگه؟

بله در حالت کلی صادقه.

(۱۷ دى ۱۳۹۰ ۰۶:۰۶ ب.ظ)NoOne نوشته شده توسط:  آیا عبارت زیر فقط برای زبانهای منظم تعریف میشه؟
مکمل زبان ال=سیگما استار منهای ال

اینم درحالت کلی صادقه.

[tex]\sum ^{*}-L=\sum ^{*}\cap \bar{L}=\bar{L}[/tex]

البته جواب آقای mfxpert کامله.

۰
ارسال:
  

narges_r پاسخ داده:

زبان تهی ومکمل آن

آیا زبان تهی مکمل سیگما استار هست؟
فکر میکنم همیشه اینطور نباشه، فکر میکنم وقتی تهی مکمل سیگما استار میشه که L برابر سیگما باشه و وقتی هم L برابر سیگما میشه که L شامل اعضای تک عضوی باشه که تمام الفبای سیگمارو پوشش بده اما گاهی اوقات L برابر سیگما نیست مثل سیگما = {۰و۱} و L={00 , 1 که در اینصورت سیگما استار - L استار برابر تهی نمیشه پس تهی هم مکمل سیگما استار نیست

آیا زبان ال منهای سیگما استار برابر با تهی است؟
فکر نمیکنم همیشه L منهای سیگما استار برابر تهی بشه باتوجه به همون موضوعی که بالا توضیح دادم، چون ممکنه L و سیگما برابر نباشن ولی اگر L و سیگما برابر باشن تفاضل L و سیگما استار برابر تهی میشه

تعریف تفاضل دو زبان به صورت اشتراک زبان اول با مکمل زبان دوم نیست مگه؟ بله تعریف همینه

آیا عبارت زیر فقط برای زبانهای منظم تعریف میشه؟ فکر نمیکنم این رابطه فقط برای زبانهای منظم باشه فکر میکنم برای همه زبانها باشه

در مورد جواب سوالها مطمئن نیستم ممکنه اشتباه باشه

۰
ارسال:
  

hadi_m پاسخ داده:

زبان تهی ومکمل آن

اگر با دید مجموعه ایی به مسئله نگاه کنیم در مورد مسئله یک من شک دارم که مکمل سیگما استار تهی بشه و در عین حال هم میتونه مکمل هم باشن
دلیلم اینه:
نخست اینکه نمیتونن مکمل هم باشن:
همانطور که میدانیم سیگما استار مجموعه مرجع هست و شامل تمام زبانها که روی ان تعریف شده اند که یکی از این زیر مجموعه‌ها هم زبان تهی هست که خودش زیر مجموعه سیگما استار هست . لذا زبان تهی نمیتونه مکمل سیگما استار باشه .

حالا با نگرش به تعریف مکمل در ریاضی و مجموعه‌ها:

اما اگر به تعریف مکمل در ریاضی نگاه کنیم . مبینیم که میتونه مکمل هم باشن چون زبان سیگما استار و زبان تهی اجماعا منجر به تولید مجموعه مرجع میشه که در این حالت مکمل هم هستن .

به نظر خودم استدلال دوم قوی‌تر باشه اما شک دارم .
دوستان اگر نظر دقیق تری نسبت به این مسئله دارن خوشحال میشم عنوان کنند و اینکه به نظرتون کدام استلال درست‌تر هست .
با تشکر .

ارسال:
  

narges_r پاسخ داده:

RE: زبان تهی ومکمل آن

(۱۹ دى ۱۳۹۰ ۰۶:۳۸ ب.ظ)hadi_m نوشته شده توسط:  ا
همانطور که میدانیم سیگما استار مجموعه مرجع هست و شامل تمام زبانها که روی ان تعریف شده اند که یکی از این زیر مجموعه‌ها هم زبان تهی هست که خودش زیر مجموعه سیگما استار هست . لذا زبان تهی نمیتونه مکمل سیگما استار باشه .

سیگما استار زبان نیست یک مجموعه است که شامل تمام رشته هایی که با الفبا ساخته میشه که شامل رشته نال هم هست که برابر لاندا میشه
اگر سیگما استار مجموعه ای از مجموعه‌ها بود شامل مجموعه تهی هم بود اما سیگما استار مجموعه ای از رشته هاست پس نمیتونه شامل مجموعه تهی باشه

فکر میکنم تهی مکمل سیگما استار باشه(درضمن استدلالهای من برای جواب سوال اول و دوم در پست قبلی من اشتباه هستSmile)
یافتن تمامی ارسال‌های این کاربر



پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close