. . .
: کارشناسی --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : یک ۱
عن-وان درس : مبانی نظریه محاسبه، نظریه اتوماتهاوزبانها، نظریه زبانها وماشین ها، نظریه زبانها وماشینها
رشته تحصیلی / کد درس : علوم کامپیوتر ۱۱۱۱۳۳۱- ، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۸۳ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر(سخت) افزار) چند بخشی ۱۱۱۵۱۵۷ - ، علوم کامپیوتر ۱۱۱۵۱۶۵
۱- اگر A مجموعه تمامی پیشوندها و پسوندهای رشته W=aabb باشد، این مجموعه چند عضو خواهد داشت؟
ү t ð . Y. \ . . Y 人.1 ۲- اگر زبان {0L* = {a"b"a"b"| n,m=0 ) . . L* = {a"b"a"b" | n >0} . L = { we (a,b) |n(w) = n(w) } { L* = {a"b"|n-0 ) . " ۳- کدام گزینه صحیح است؟
۱. اگر برای یک زبان، گرامر خطی موجود باشد، آن زبان حتماً منظم است.
۲. اگر برای یک زبان، گرامر خطی چپ موجود باشد، زبان آن گرامر منظم است.
۳. گرامرهای به فرم چامسکی، فقط برای توصیف زبانهای متناهی بکار می روند.
۴. یک گرامر به فرم نرمال گریباخ، حتما از نوع S-گرامر هم هست.
۴- زبان گرامر زیر چیست؟
S — A | B A –> aAb | C C —> aC | a B –» aBb | D
Ꭰ -> bᎠ | b
L = {a"b"| nom} Y L = {a"b" | n+m} . \ L = {a"b"| n,m=0} . * L = {a"b"| n>m} U {a"b" | n >0} . Y 1010/10.10443 نیمسال دوم ۹۱-۱۳۹۰ صفحه ۱ از ۱۶




***
. . . 藥 = دانشگاه پیام نور کارشناسی مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست
تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : یک ۱ عن-وان درس : مبانی نظریه محاسبه، نظریه اتوماتهاوزبانها، نظریه زبانها وماشین ها، نظریه زبانها وماشینها رشته تحصیلی / کد درس : علوم کامپیوتر ۱۱۱۱۳۳۱- ، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۸۳ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات
چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر(سخت) افزار) چند بخشی ۱۱۱۵۱۵۷ - ، علوم کامپیوتر ۱۱۱۵۱۶۵
۵- کدامیک از گزینه های زیر عبارت منظم مناسبی برای زبان L ارائه می دهد؟
{w دارای دقیقاً یک زوج صفر متوالی باشد ا" {0,1}L={we
(0+1)"00(1+0)' . . (1+01).00(1+10) .)
(010) 00(010) (O1)"00(10) v
۶- کدام گزینه توصیف مناسبی برای ماشین حالت متناهی )DFA( زیر می باشد.
L = { we(a,b) (n(w)-n(w) mod 3 = 0} L = { we{a,b) | n,(w) mod 3 # n.(w) mod 3 } ' '
r
L = { we(a,b) | lwl mod 3 = na(w) mod 3 } ·
L = { we(a,b) |n(w) mod 3 > n(w) mod 3 } ."
1,\·/\,\,FF*
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۲ از ۱۶




***
. . .
: کارشناسی --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : ۱ یک
عن-وان درس : مبانی نظریه محاسبه، نظریه اتوماتهاوزبانها، نظریه زبانها وماشین ها، نظریه زبانها وماشینها رشته تحصیلی / کد درس : علوم کامپیوتر ۱۱۱۱۳۳۱- ، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۸۳ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر(سخت افزار) چند بخشی ۱۱۱۵۱۵۷ - ، علوم کامپیوتر ۱۱۱۵۱۶۵
۷- فرض کنید که زبان L به شکل {L = {ab, aa,baa است. در این صورت کدام یک از رشته های زیر در L قرار دارند؟ baabaaabbaaba . Y aabaaaaabbaaababaa . )
baaabaaabaaaabaaa : * abababaabaabaaabaaabb - Y
۸- اگر نماد ۸ رشته تهی را نشان دهد، زبان پذیرفته شده توسط ماشین حالت متناهی داده شده، معادل کدام یک از عبارات
b a, b X4 baab+abaab. " A+ (a+b) bab :) A+ (a+b)(bb) a(a+b) * A4 (a+b)b a(a+b) v.
۹- با توجه به دو زبان L1 و L2 کدامیک از گزینه های زیر نادرست است؟ LI={a"b" | n^m}
L3={a"b" | n,m=0}
L1 r` L2 = L1 Y L1 U L2 = L2 . )
-- . Y. - I .,= { a"Ꮒ" | n>0 } . Ý L = {a"b" In 20) L¬- L|={a"b" | n>0}
1010/10.10443
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۳ از ۱۶









***
. . .
: کارشناسی --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : یک ۱
عن-وان درس : مبانی نظریه محاسبه، نظریه اتوماتهاوزبانها، نظریه زبانها وماشین ها، نظریه زبانها وماشینها
رشته تحصیلی / کد درس : علوم کامپیوتر ۱۱۱۱۳۳۱- ، مهندسی کامپیوتر(نرم افزار) ۱۱۱۵۰۸۳ - ، مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات چند بخشی )، مهندسی کامپیوتر - نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر(سخت) افزار) چند بخشی ۱۱۱۵۱۵۷ - ، علوم کامپیوتر ۱۱۱۵۱۶۵
.W— عبارتهای منظم r1 و r2 9 گرامرهای G2 3 G1 به صورت زیر هستند. اگر )1.L2=L(r2) 3 LI=L(r 3 نیز (L3=L(G1 و (L4=L(G2 باشند. کدام گزینه صحیح است؟
r1 = (aa)*a(bb)* r2 = (aa)*(bb)*b
G1: S–> ABb A— a/Aal A B–> bBb | A
G2: S–> aA A—» aS | aB B— b{U C—» bB | A
L1 = L4 3 L2 = L3 ‘ L = L3 ; L = L. "
L2 # L = L3 = LA Y L1 # L2 = L3 = L4 -"
1010/10.10443
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۴ از ۱۶

***