Pages

Senin, 08 Oktober 2012

Beberapa Sifat Operasi pada Teori Bahasa dan Automata



·         Tidak selalu berlaku : x = Prefix(x)Postfix(x)
·         Selalu berlaku : x = Head(x)Tail(x)
·         Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x)
·         Selalu berlaku : ProperPrefix(x) ¹ ProperPostfix(x)
·         Selalu berlaku : Head(x) ¹ Tail(x)
·         Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya
·         Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya
·         Dua sifat aljabar concatenation :
¨      Operasi concatenation bersifat asosiatif : x(yz) = (xy)z
¨      Elemen identitas operasi concatenation adalah e : ex = xe = x
·         Tiga sifat aljabar alternation :
¨      Operasi alternation bersifat komutatif : x½y = y½x
¨      Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z
¨      Elemen identitas operasi alternation adalah dirinya sendiri : x½x = x
·         Sifat distributif concatenation terhadap alternation : x (y½z) = xy½xz
·         Beberapa kesamaan :
¨      Kesamaan ke-1 : (x*)* = x*
¨      Kesamaan ke-2 : e½x = x½e = x*
¨      Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.

Tidak ada komentar:

Posting Komentar