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

ضروری زبان های منظم

ارسال:
  

javadjj پرسیده:

ضروری زبان های منظم

سلام دوستان سوالی در مورد مفهوم زبان های منظم
چرا زبان{a^nb^n} در صورتی که بزرگتر مساوی از صفر باشه منظم نیست
ببینید یه دلیل مفهومی خوب میخوام من اینو میدونم که منظم نیست اما از کسی
که میدونه میخوام برام کامل توضیح بده ترجیحا با مثال

۰
ارسال:
  

luna پاسخ داده:

ضروری زبان های منظم

زبان های منظم حافظه ندارند ولی برای این زبان ما به حافظه احتیاج داریم که تعداد a ‌ها رو نگه داره!

۰
ارسال:
  

Afra پاسخ داده:

ضروری زبان های منظم

بینید زمانی که مقدار n=0 هست در واقع عبارت ۱ را داریم که به راحتی قابل درک هست و یک عبارت منظم هست.
اما برای مقادیر n>=1 به ترتیب خواهیم داشت
....ab, aabb, aaabbb, aaaabbbb

در نتیجه، همانطور که لونا‌ی عزیز گفتند، برای رسم،به حافظه ای نیاز داریم که تعداد تکرار های a را نگه داشته و b را به همان تعداد تکرار کند.

۰
ارسال:
  

karostami پاسخ داده:

ضروری زبان های منظم

یکی از مهمترین محدودیتهای زبانهای منظم اینه که حافظه ندارند. زبانهایی که لازمه تعداد تکرارهای مشخصی را حفظ کنند مانند این زبان منظم نیست. در واقع شما نمی توانید هیچ اتاماتای معینی برایشان رسم کنید.
چنانچه بتونید خوب آتاماتا بکشید برای زبانها به راحتی می توانید مشخص کنید که زبان چه نوعی است. که این هم بیش از هر چیز دیگه احتیاج به تمرین دارد.

۰
ارسال:
  

javadjj پاسخ داده:

ضروری زبان های منظم

ممنون از راهنمایی همه دوستان عزیز!!!
اما خوب نمیشه یه وضعیت Q1 ایجاد کنیم و دوتا حلقه براش بزاریم و با a,b برچسب بزنیم همین وضعیت نهایی هم باشه
همین ماشین این زبان رو بپذیره اما خوب این ماشین رشته هایی که a,b مساوی هم نباشند رو می پذیره
آیا این میتونه دلیل بر این باشه که ماشین مربوط به این زبان نیست.
زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بود و نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
میخوام نتیجه بگیرم که اگر تستی دادند به این صورت اگه ما یه مثال نقض پیدا کنیم درسته دیگه اره.
مطلب دیگه ای تو یه کتاب خوندم این بود وابستگی بین تعداد a,b‌ها وجود نداشته باشه که اینجا هست

ارسال:
  

Soheil پاسخ داده:

RE: ضروری زبان های منظم

(۲۸ شهریور ۱۳۸۹ ۰۱:۴۵ ب.ظ)javadjj نوشته شده توسط:  زمانی که سوال میدن a^3 سه حالت q1,q2,q3 رسم و q3 حالت پایانی اما چون اینجا n مشخص نیست شاید n عدد بزرگی بودو نتونستیم اینقدر حال ایجاد کنیم منظور از حافظه میشه گفت یه جورایی همینه دیگه.
مشکل اندازه n نیست، مشکل عدم وجود حافظه در زبانهای منظمه که نمیتونه تعداد aها رو نگه داره تا bها رو هم به همون اندازه قبول کنه! اگه تو تستها یه عدد خیلی خیلی بزرگ مشخص هم به جای n بدن اون زبان منظمه (حتی اگه استفاده از اون تعداد حالت در ماشینمون غیرمعقول باشه)
در واقع حافظه در حد "هیچ" هستش نه "کم"!
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

karostami پاسخ داده:

ضروری زبان های منظم

بله. ماشینی که شما برای این زبان طراحی کردید( یک وضعیت که همان هم نهایی باشه) ماشین این زبان نیست چون این زبان روی الفبای a,b تمامی رشته ها، بدون وابستگی به تعداد، را می پذیرد.
حافظه هم تقریبا همین معنا را می دهد. ماشینی که a^3 را می پذیرد، همانی که شما گفتید، دارای حافظه محدود است به طول ۳/ ولی چون تعداد n نامشخص و می تواند بی نهایت باشد شما نمی تونید همچین ماشین معینی را بکشید. دقت کنید حتی اگر زبان a^1000b^1000 بود چون n محدود است منظم است و شما می تونید چنین ماشینی را بکشید. حتی اگر در تعریف زبان a^nb^n محدودیتی مانند n<1000 تعریف شده باشد هم می توان ماشینی کشید. چون تشخیص این زبان با آنکه نیاز به حافظه دارد ولی حافظه نامحدود لازم ندارد.

۰
ارسال:
  

javadjj پاسخ داده:

ضروری زبان های منظم

ممنون کاملا فهمیدم

۰
ارسال:
  

javadjj پاسخ داده:

ضروری زبان های منظم

امروز تو کتاب لینز خوندم a^nb^l:l<>n منظم نیست یکی دلیلشو بگه لطفه

ارسال: #۱۰
  

saria پاسخ داده:

RE: ضروری زبان های منظم

(۱۷ مهر ۱۳۸۹ ۰۷:۳۲ ب.ظ)javadjj نوشته شده توسط:  امروز تو کتاب لینز خوندم a^nb^l:l<>n منظم نیست یکی دلیلشو بگه لطفه
خوب میتونی اینو با مثال حل کنی
اگه L منظم باشه پس ال بارهم منظمه
ال بار=a^nb^n
پس ال بار اشتراکش با L1=a^nb^l باید منظم باشه
a^nb^n اشتراکش با a^nb^l مساوی a^nb^n که در نتیجه چون میدونیم که
a^nb^n حتما نامنظمه و اشتراک ۲ زبان منظم نمیتونه نامنظم باشه پس زبان مورد بحث نامنظم است

بد گفتم ولی چند بار بخونیش متوجه میشیBig Grin[/u]
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۱
  

luna پاسخ داده:

ضروری زبان های منظم

چون احتیاج به حافظه داره! که حالت l=n رو قبول نکنه!

۰
ارسال: #۱۲
  

ف.ش پاسخ داده:

ضروری زبان های منظم

به خاطر اینکه گفته n#l و ما نمیتونیم براش محدودیت ایجاد کنیم که n برابر l نشه. اگر شرط رو برداریم

این همون a^nb^l منهای a^nb^n است که زبان اول منظم ولی زبان دوم منظم نیست.


اگر l عدد ثابتی بود میتوانستیم به عنوان یک تله حالت n=عدد ثابت = ۵ را به عنوان حالت عدم پذیرش لحاظ کنیم اما چون ثابت نیست نمیتوانیم .



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۶,۰۸۵ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  گرامر زبان انگلیسی:صفت های ed و ing دار cyruskingsolomon ۳ ۳,۱۶۵ ۱۵ بهمن ۱۳۹۹ ۰۶:۴۱ ب.ظ
آخرین ارسال: cyruskingsolomon
  گرامر منظم Sanazzz ۶ ۷,۰۸۹ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
Photo ساده سازی عبارت منظم etedadi ۰ ۲,۱۳۶ ۱۶ خرداد ۱۳۹۷ ۰۷:۰۴ ب.ظ
آخرین ارسال: etedadi
  نیاز به راهنمایی و تجربه دوستان (ضروری) امیر ای تی ۷ ۶,۱۸۵ ۱۳ خرداد ۱۳۹۷ ۱۱:۰۱ ب.ظ
آخرین ارسال: Parisa__karimi
  روش مناسب من کدام است؟ ۸ تا از بهترین روش های یادگیری لغات زبان انگلیسی moeintnt ۰ ۱,۹۷۶ ۳۰ دى ۱۳۹۶ ۰۸:۲۵ ب.ظ
آخرین ارسال: moeintnt
  عبارت منظم fsmtnc ۱ ۲,۱۳۳ ۲۱ دى ۱۳۹۶ ۰۶:۵۵ ب.ظ
آخرین ارسال: msour44
  گرامر منظم fsmtnc ۲ ۳,۰۲۶ ۱۴ دى ۱۳۹۶ ۱۱:۵۷ ق.ظ
آخرین ارسال: fsmtnc
  معرفی دیکشنری برای زبان های آلمانی و فرانسه roozbeh.rahmani ۰ ۲,۲۸۳ ۰۵ دى ۱۳۹۶ ۰۳:۱۶ ب.ظ
آخرین ارسال: roozbeh.rahmani
  تست های گرامر زبان عمومی ارشد (با پاسخ های تشریحی) ali.arr74 ۰ ۲,۸۴۶ ۱۳ مهر ۱۳۹۶ ۰۱:۲۰ ب.ظ
آخرین ارسال: ali.arr74

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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