فرق این دو زبان و گرامراشون چی هس؟
[tex]L_9=\{w\in\{a,b\}^*:n_a(w)=n_b(w),w=uv,n_a(u)>=n_b(u)\}[/tex]
[tex]L_7=\{w\in\{a,b\}^*:n_a(w)=n_b(w)\}[/tex]
سلام. وقت بخیر.
اگه امکانش هست رابطه ها رو تو TEX بنویسید. نتونستم بخونمشون.
(۲۷ فروردین ۱۳۹۵ ۰۶:۳۳ ب.ظ)dokhtare payiz نوشته شده توسط: فرق این دو زبان و گرامراشون چی هس؟سلام.زبان L9 که میگه که رشته هایی که تعداد aها و b هاشون مساوی باشه و همچنین در هر پیشوندی از رشته ها،تعداد a ها بزرگتر مساوی تعداد b ها باشه.(صورت سوالتون اصلا واضح نیست.اینجا دوباره نوشتمش)
[tex]L_9\: =\: \{w\epsilon\: \{a,b\}^{\ast}\: : \: n_a(w)=n_b(w)\: \: ,\: \: \: w=uv\: \: ,\: n_a(u)\ge n_b(u)\}[/tex]
مثلا رشته ی baab به این زبان تعلق نداره،چونکه اگه u=b و v=aab قرار بدیم،شرط زبان برقرار نیست و در u تعداد aها بزرگتر مساوی تعداد bها نیست.
ولی رشته ی abab به این زبان تعلق داره.
و گرامر های زیر هم میتونند که گرامر این زبان باشند:
[tex]S\: \: \rightarrow\: \: aSbS\: \mid\: \: \lambda[/tex]
[tex]S\: \: \rightarrow\: \: SaSb\: \mid\: \: \lambda[/tex]
[tex]S\: \: \rightarrow\: \: aSb\: \mid\: SS\: \mid\: \: \lambda[/tex]
که یک زبان مستقل از متن هستش.[tex]S\: \: \rightarrow\: \: SaSb\: \mid\: \: \lambda[/tex]
[tex]S\: \: \rightarrow\: \: aSb\: \mid\: SS\: \mid\: \: \lambda[/tex]
---------------------------------------------------------
ولی L7 شامل رشته هایی است که تعداد aها و b های آنها یکسان باشد.
[tex]L_7\: =\: \{w\epsilon\: \{a,b\}^{\ast}\: :\: n_a(w)=n_b(w)\: \}[/tex]
و زبان L9 (اولی )زیرمجموعه این زبان هستش. این زبان هم یک زبان مستقل از متن هستش. و این زبان رشته هایی مثل baab و abab رو میتونه بپذیره.
و گرامر های زیر مربوط به این زبانند:
[tex]S\: \rightarrow\: \: aSbS\: \mid\: \: bSaS\: \mid\: \lambda\: [/tex]
[tex]S\: \rightarrow\: \: SaSb\: \mid\: \: SbSa\: \mid\: \lambda\: [/tex]
[tex]S\: \rightarrow\: \: aSb\: \mid\: \: bSa\: \mid\: SS\: \mid\: \lambda[/tex]
[tex]S\: \rightarrow\: \: SaSb\: \mid\: \: SbSa\: \mid\: \lambda\: [/tex]
[tex]S\: \rightarrow\: \: aSb\: \mid\: \: bSa\: \mid\: SS\: \mid\: \lambda[/tex]
(۰۲ اردیبهشت ۱۳۹۵ ۰۳:۴۵ ب.ظ)IranianWizard نوشته شده توسط:ممنون, تنها فرقشون اینکه تو اولی رشته ها نباید با b شروع شن.(27 فروردین ۱۳۹۵ ۰۶:۳۳ ب.ظ)dokhtare payiz نوشته شده توسط: فرق این دو زبان و گرامراشون چی هس؟سلام.زبان L9 که میگه که رشته هایی که تعداد aها و b هاشون مساوی باشه و همچنین در هر پیشوندی از رشته ها،تعداد a ها بزرگتر مساوی تعداد b ها باشه.(صورت سوالتون اصلا واضح نیست.اینجا دوباره نوشتمش)
[tex]L_9\: =\: \{w\epsilon\: \{a,b\}^{\ast}\: : \: n_a(w)=n_b(w)\: \: ,\: \: \: w=uv\: \: ,\: n_a(u)\ge n_b(u)\}[/tex]
مثلا رشته ی baab به این زبان تعلق نداره،چونکه اگه u=b و v=aab قرار بدیم،شرط زبان برقرار نیست و در u تعداد aها بزرگتر مساوی تعداد bها نیست.
ولی رشته ی abab به این زبان تعلق داره.
و گرامر های زیر هم میتونند که گرامر این زبان باشند:
[tex]S\: \: \rightarrow\: \: aSbS\: \mid\: \: \lambda[/tex]که یک زبان مستقل از متن هستش.
[tex]S\: \: \rightarrow\: \: SaSb\: \mid\: \: \lambda[/tex]
[tex]S\: \: \rightarrow\: \: aSb\: \mid\: SS\: \mid\: \: \lambda[/tex]
---------------------------------------------------------
ولی L7 شامل رشته هایی است که تعداد aها و b های آنها یکسان باشد.
[tex]L_7\: =\: \{w\epsilon\: \{a,b\}^{\ast}\: :\: n_a(w)=n_b(w)\: \}[/tex]
و زبان L9 (اولی )زیرمجموعه این زبان هستش. این زبان هم یک زبان مستقل از متن هستش. و این زبان رشته هایی مثل baab و abab رو میتونه بپذیره.
و گرامر های زیر مربوط به این زبانند:
[tex]S\: \rightarrow\: \: aSbS\: \mid\: \: bSaS\: \mid\: \lambda\: [/tex]
[tex]S\: \rightarrow\: \: SaSb\: \mid\: \: SbSa\: \mid\: \lambda\: [/tex]
[tex]S\: \rightarrow\: \: aSb\: \mid\: \: bSa\: \mid\: SS\: \mid\: \lambda[/tex]
(۰۵ اردیبهشت ۱۳۹۵ ۰۴:۴۰ ب.ظ)dokhtare payiz نوشته شده توسط: ممنون, تنها فرقشون اینکه تو اولی رشته ها نباید با b شروع شن.
خیر. توی هیچ زیررشته سمت چپی از رشته پذیرفته شده نباید تعداد b ها بیشتر از aها باشه. مثلاً abba پذیرفته نیست. اگه قراره با پشته پیاده سازی بشه وقتی یه b تو رشته ببینیم باید حداقل یه a تو پشته داشته باشیم.