۱
subtitle
ارسال: #۱
  
سوال ۵۴ کنکور سال ۹۴- تشخیص نوع زبان
باسلام
می خواستم بدونم این گرامر چه نوع زبانی را معرفی میکند. کلید سنجش ، گزینه ی " یک زبان مستقل از متن و خطی" بوده است.
با تشکر
می خواستم بدونم این گرامر چه نوع زبانی را معرفی میکند. کلید سنجش ، گزینه ی " یک زبان مستقل از متن و خطی" بوده است.
با تشکر
۱
ارسال: #۲
  
RE: سوال ۵۴ کنکور سال ۹۴- تشخیص نوع زبان
سلام.گزینه سنجش درسته.
اینجا یه گرامر وابسته به متن رو داده ،ولی سوال،زبان این گرامر رو خواسته!
خب باید با اشتقاق ،چند رشته از این گرامر رو تولید کنی،که ببینی زبانش چیه.
که اگه اشتقاق بدی،رشته های تولیدی میشه:
[tex]a\: \: ,\: \: a^2b^2\: ,\: \: a^3b^4\: ,\: \: a^4b^6\: ,\: a^5b^8\: ,\: \: a^6b^{10}\: ,\: \: ...[/tex]
که زبان این رشته ها میشه:
[tex]L(G)\: =\{a^na\: b^{2n}\: \: :\: n\ge0\}[/tex]
که این یک زبان خطی هستش،چون میشه واسش یه گرامر خطی به شکل زیر بدست آورد.(یک گرامر مستقل از متن با این محدودیت که سمت راست قواعد آن،حداکثر یک متغیر داشته باشه،گرامری خطی هستش)
[tex]S\: \longrightarrow\: aSbb\: |\: a[/tex]
اینجا یه گرامر وابسته به متن رو داده ،ولی سوال،زبان این گرامر رو خواسته!
خب باید با اشتقاق ،چند رشته از این گرامر رو تولید کنی،که ببینی زبانش چیه.
که اگه اشتقاق بدی،رشته های تولیدی میشه:
[tex]a\: \: ,\: \: a^2b^2\: ,\: \: a^3b^4\: ,\: \: a^4b^6\: ,\: a^5b^8\: ,\: \: a^6b^{10}\: ,\: \: ...[/tex]
که زبان این رشته ها میشه:
[tex]L(G)\: =\{a^na\: b^{2n}\: \: :\: n\ge0\}[/tex]
که این یک زبان خطی هستش،چون میشه واسش یه گرامر خطی به شکل زیر بدست آورد.(یک گرامر مستقل از متن با این محدودیت که سمت راست قواعد آن،حداکثر یک متغیر داشته باشه،گرامری خطی هستش)
[tex]S\: \longrightarrow\: aSbb\: |\: a[/tex]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close