Karadeniz Teknik Üniversitesi
Bilgisayar Mühendisliği Bölümü
Öğr.Gör. Ömer ÇAKIR
BIL348 Otomata Teorisi
1. Arasınav, 8.4.2014, 13:00, D1-2
Süre : 75 Dakika
Sınavda Uyulması Gereken Kurallar
1. Cep telefonlarının, hesap makinesi, saate bakmak gibi herhangi bir amaçla kullanılması yasaktır. Telefon kapalı ve cepte olmalıdır.
2. Sınavın başında öğrenciler anlamadıkları noktaları sesli olarak sorup, Hoca cevapladıktan sonra sınav boyunca soru sormak yasaktır.
NUMARA :
AD SOYAD :
DEĞERLENDİRME :
S  AA
A  AS | AB | BA | a
B b
1.
“ab ile biten tüm kelimelerin dili” için :
a) RE yazınız. (5P)
b) nondeterministic FA çiziniz. (10P)
c) nondeterministic FA’i deterministic FA’e çeviriniz.
(15P)
İpucu  Hem nondeterministic FA hem de deterministic FA 3
durumludur.
2.
Yukarıdaki gramerin aşağıdaki nondeterministic PDA
eşdeğerini ve tabloyu kullanarak babaaa kelimesi için parse
ağacını çiziniz. (30P)
START
A
0
B
PO
P
nondeterministic FA
PUSH S
S
l
A
A
A
RE
A
3 D
a
RE
A
2 D
RE =
RE
A
1 D
b
PUSH A
PUSH S
PUSH B
PUSH A
PUSH A
PUSH A
PUSH A
PUSH B
l
ACCEPT
deterministic FA tüm durumlar
01
02
03
04
05
06
07
08
09
10
11
12
13
14
deterministic FA son hali
15
State
Push S
Pop
Push A
Push A
Pop
Push S
Push A
Pop
Push A
Push B
Pop
Read 2
Pop
Read 1
Pop
Stack
S
l
A
AA
A
SA
ASA
SA
ASA
BASA
ASA
ASA
SA
SA
A
Tape
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Push A
Push A
Pop
Push A
Push B
Pop
Read 2
Pop
Read 1
Pop
Read 1
Pop
Read 1
Pop
Read 3
Accept
AA
AAA
AA
AAA
BAAA
AAA
AAA
AA
AA
A
A
l
l
l
l
l
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
babaaa
3. soru arka sayfadadır 
3.
a)
b)
c)
d)
Yukarıdaki FA’deki durumları :
q3,q2,q1 sırasında silerek RE elde ediniz. (10P)
q3,q1,q2 sırasında silerek RE elde ediniz. (10P)
q1,q3,q2 sırasında silerek RE elde ediniz. (10P)
q2,q3,q1 sırasında silerek RE elde ediniz. (10P)
Download

Sorular - Karadeniz Teknik Üniversitesi