Biçimsel Diller ve
Soyut Makineler
Hafta2
1
Hesaplama
CPU
Hafıza
2
Geçici bellek
input bellek
CPU
output bellek
Program bellek
3
Örnek: f ( x )  x
3
Geçici bellek
input bellek
CPU
output bellek
Program bellek
compute
xx
compute
2
x x
4
f ( x)  x
3
temporary memory
input memory
x2
CPU
Program memory
output memory
compute x  x
compute x 2  x
5
temporary memory
z  2*2  4
f ( x)  x
3
f ( x)  z * 2  8
input memory
x2
CPU
output memory
Program memory
compute
xx
compute
2
x x
6
temporary memory
z  2*2  4
f ( x)  z * 2  8
f ( x)  x
3
input memory
x2
CPU
f ( x)  8
Program memory
output memory
compute x  x
2
compute x  x
7
Otomat
temporary memory
Automaton
input memory
CPU
output memory
Program memory
8
Farklı otomat çeşitleri
Otomatlar geçici bellek kullanımlarına göre ayırdedilirler
• Finite Automata:
• Pushdown Automata:
• Turing Machines:
bellekleri yoktur.
yığıt
random access memory
9
Finite Automaton
temporary memory
Finite
Automaton
input memory
output memory
Örnek: Vending Machines
(Hesap gücü düşük)
10
Pushdown Automaton
Stack
Push, Pop
Pushdown
Automaton
input memory
output memory
Örnek:Programlama Dili derleyicileri
(Hesaplama Gücü orta)
11
Turing Makinesi
Random Access Memory
Turing
Makinesi
input memory
output memory
Örnek: Herhangi bir Algoritma
(Hesaplama gücü en yüksek)
12
Otomatların Güçleri
Finite
Pushdown
Automata
Turing
Automata
Makinesi
Az güç
Basit
problemler
Yüksek güç
Daha karmaşık
13
problemler
DİLLER
Dil:Karakter katarları kümesidir.
Bir alfabe üzeründe tanımlı
Karakter (letter) dizisidir.
Katar (String):
  a , b , c ,  , z 
Examples: “for”, “while”, “toplam”, …
14
Alphabets and Strings
  a , b 
Alfabemiz
Strings
a
ab
u  ab
abba
v  bbbaaa
baba
w  abba
aaabbbaaba b
15
String işlemleri
w  a1 a 2  a n
abba
v  b1b 2  b m
bbbaaa
Concatenation
wv  a1 a 2  a n b1b 2  b m
abbabbbaaa
16
Reverse
w  a1 a 2  a n
w
R
 a n  a 2 a1
ababaaabbb
bbbaaababa
17
Katar uzunluğu
w  a1 a 2  a n
w n
Uzunluk:
Örnekler:
abba  4
aa  2
a 1
18
Bitiştirme’nin uzunluğu
uv  u  v
u  aab ,
Örnek:
u 3
v  abaab ,
v 5
uv  aababaab
8
uv  u  v  3  5  819
Empty String
Sıfır karakterden oluşan katar:
 ( ,  )
 0
Observations:
w  w   w
 abba  abba   abba
20
Alt katar (Substring)
String
Substring
abbab
ab
abbab
abba
abbab
b
abbab
bbab
21
Prefix and Suffix
Prefixes

a
ab
abbab
Suffixes
abbab
w  uv
bbab
bab
abb
ab
abba
b
abbab

prefix suffix
22
Üs işlemi
w
n
 ww

w



n
Örnek:
 abba   abbaabba
2
Tanım:
0
w 
 abba   
0
23
* (kleene) işlemi
* 
:
üzerinde tanımlı Olası bütün katarlar kümesi
  a , b 
 *   , a , b , aa , ab , ba , bb , aaa , aab ,  
24
+ işlemi

 :  dışında,  üzerinde tanımlı
olası bütün katarlar
  a , b 
 *   , a , b , aa , ab , ba , bb , aaa , aab ,  


  * 


 a , b , aa , ab , ba , bb , aaa , aab25,  
Languages
Dil
 *‘ in herhangi bir alt kümesi olarak tanımlanabilir.
Örnek:
Diller:
  a , b 
 *   , a , b , aa , ab , ba , bb , aaa ,  
 
a , aa , aab 
{  , abba , baba , aa , ab , aaaaaa }
26
Dikkat
Sets
  { }  { }
Set size
{}    0
Set size
{ }  1
String length
 0
27
Örnek
n
L  {a b
n
: n  0}

ab
L
abb  L
aabb
aaaaabbbbb
28
Diller üzerinde işlemler
a , ab , aaaa   bb , ab   { a , ab , bb , aaaa }
Genel Küme İşlemleri:
a , ab , aaaa   bb , ab   { ab }
a , ab , aaaa   bb , ab   a , aaaa 
Tümleyen:
L   * L
a , ba    , b , aa , ab , bb , aaa ,  
29
Reverse
L
Tanım:
R
 {w
R
: w  L}
ab , aab , baba   ba , baa , abab 
R
Örnek:
n
n
L  { a b : n  0}
R
L ?
30
Reverse
L
Tanım:
R
 {w
R
: w  L}
ab , aab , baba   ba , baa , abab 
R
Örnek:
n n
L  { a b : n  0}
L
R
n n
 {b a : n  0}
31
Bitiştirme (Concatenation)
L1 L 2   xy : x  L1 , y  L 2 
Tanım:
Örnek:
a , ab , ba b , aa 
 ab , aaa , abb , abaa , bab , baaa 
32
Üs işlemi
n
L 
LL
L
n
Definition:
a , b   a , b a , b a , b  
3
aaa , aab , aba , abb , baa , bab , bba , bbb 
Özel Durum:
0
L   
a , bba , aaa 0   
33
Örnek
n n
L  { a b : n  0}
2
n n m m
L  {a b a b
aabbaaabbb
: n , m  0}
L
2
34
Yıldız Kapanma-Star-Closure
(Kleene *)
0
1
2
L*  L  L  L 
Tanım:
 ,

Örnek:
 a , bb ,



a , bb *  

aa
,
abb
,
bba
,
bbbb
,


 aaa , aabb , abba , abbbb ,  
35
Pozitif Kapanma-Positive
Closure

1
2
L  L  L 
Tanım:
 L *   
 a , bb ,




a , bb    aa , abb , bba , bbbb ,

 aaa , aabb , abba , abbbb ,  


36
Download

Languages and Finite Automata