Operasi Dasar String ~ Prerfix & ProperPerfix

Prefix

“string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang string tersebut .”

ProperPrefix

“string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang string tersebut .”

Contoh:

Misalkan 

String(x)= 100100, maka

Prefix(x)= 100100, 10010, 1001, 100, 10, 1, dan Φ

ProperPrefix(x) = 10010, 1001, 100, 10, 1, dan Φ

Berikut prosesnya:

String (x)	1	0	0	1	0	0
Prefix(x)	1	0	0	1	0	0
	1	0	0	1	0
	1	0	0	1
	1	0	0
	1	0
	1
	⏀
ProperPrefix(x)	1	0	0	1	0
	1	0	0	1
	1	0	0
	1	0
	1
	⏀

Simple Design of Automata

look a sample simple design of Automata:

Five tuple (Q,Σ,δ,q0,F):
Q	: states	:{q0,q1}
Σ	: alphabet (input)	:{0,1}
q0	: start states	: q0
F	: final/accept states	:{q1}
δ	: transition function	:

δ	0	1
q0	q1	{}
q1	{}	q0

A recognized string is a string that starts in the initial state and ends in the final state. 

For example:

The recognized string is:"0", "010", "01010",..., "0(10)*".

1). q0 -> q1= 0
2). q0 -> q1 -> q0 -> q1= 010
3)....

Design Non-Deterministic Finite Automata 1

We can design the NFA with 3 states and the rule is: the string that can be received must end in 'ab'.
Examples of strings that can be accepted: 

• 'ab', 
• 'aab', 
• 'a * ab', 
• 'bab',
• 'b * ab', 
• 'abab', 
• 'a * b * ab', 
• 'b * a * ab '

The  Answer: 

 

Design the NFA 

 

UTS TBO 2016/2017

1.  Diberikan string (x) = aku , sebutkanlah;

a)      ProperPrefix (x)

b)      Postfix (x)

c)      Head (x)

d)     Tail (x)

e)      ProperSubstring (x)

f)       Subsequence (x)

2. Reduksilah state  DFA berikut ;
 

jawaban: 

1    1.Diketahui string (x) = aku , maka;

a)      ProperPrefix (x) = ak, a, ϵ

b)      Postfix (x) = aku, ku, u, ϵ

c)      Head (x) = a

d)     Tail (x) = u

e)      ProperSubstring (x) = ak, u, a, ku, k, ϵ

f)       Subsequence (x) = aku, ak, u, a, ku, k, au, ϵ

 2. a) state yang dihapus q2,

     b) pasangan state:

         (q0,q1),(q0,q3),(q0,q4),(q0,q5),(q0,q6),

         (q1,q3),(q1,q4),(q1,q5),(q1,q6),

         (q3,q4),(q3,q5),(q3,q6),

         (q4,q5),(q4,q6),

         (q5,q6).

     c) berikan predikat distinguishable(dapat dibedakan), jika pasangan state salah satunya adalah final state;

         (q0,q1)

         (q0,q3)

         (q0,q4)

         (q0,q5)

         (q0,q6) Distinguishable

         (q1,q3)

         (q1,q4)

         (q1,q5)

         (q1,q6) Distinguishable

         (q3,q4)

         (q3,q5)

         (q3,q6) Distinguishable

         (q4,q5)

         (q4,q6) Distinguishable

         (q5,q6) Distinguishable

     d) cari predikat pasangan state yang lainnya;

         (q0,q1)

          ᵟ(q0,a) = q1

          ᵟ(q1,a) = q5      

     ᵟ(q0,b) = q3

     ᵟ(q1,b) = q1 (indistinguishable)

         (q0,q3)

        
     ᵟ(q0,a) = q1

          ᵟ(q3,a) = q5       

     ᵟ(q0,b) = q3

     ᵟ(q3,b) = q1 (indistinguishable)

         (q0,q4)

          ᵟ(q0,a) = q1

          ᵟ(q4,a) = q4       

     ᵟ(q0,b) = q3

     ᵟ(q4,b) = q6 (distinguishable)

         (q0,q5)

         ᵟ(q0,a) = q1

          ᵟ(q5,a) = q4       

     ᵟ(q0,b) = q3

     ᵟ(q5,b) = q6 (distinguishable)     
          (q1,q3)

          ᵟ(q1,a) = q5

          ᵟ(q3,a) = q5       

     ᵟ(q1,b) = q1

     ᵟ(q3,b) = q1 (indistinguishable)

         (q1,q4)

          ᵟ(q1,a) = q5

          ᵟ(q4,a) = q4       

     ᵟ(q1,b) = q1

     ᵟ(q4,b) =  q6 (distinguishable)

         (q1,q5)

          ᵟ(q1,a) = q5

          ᵟ(q5,a) = q4      

     ᵟ(q1,b) = q1

     ᵟ(q5,b) = q6 (distinguishable)

         (q3,q4)

          ᵟ(q3,a) = q5

          ᵟ(q4,a) = q4       

     ᵟ(q3,b) = q1

     ᵟ(q4,b) = q6 (distinguishable)

         (q3,q5)

          ᵟ(q3,a) = q5

          ᵟ(q5,a) = q4       

     ᵟ(q3,b) = q1

     ᵟ(q5,b) = q6 (distinguishable)

         (q4,q5)

          ᵟ(q4,a) = q4

          ᵟ(q5,a) = q4       

     ᵟ(q4,b) = q6

     ᵟ(q5,b) = q6 (indistinguishable)

         dengan demikian;
         (q0,q1) Indistinguishable

         (q0,q3) Indistinguishable

         (q0,q4) Distingushable

         (q0,q5) Distingushable

         (q0,q6) Distingushable

         (q1,q3) Indistinguishable

         (q1,q4) Distingushable

         (q1,q5) Distingushable

         (q1,q6) Distingushable

         (q3,q4) Distingushable

         (q3,q5) Distingushable

         (q3,q6) Distingushable

         (q4,q5) Indistinguishable

         (q4,q6) Distingushable

         (q5,q6) Distingushable

     e)  kelompokan pasangan state yang indistinguishable yaitu (q0,q1), (q0,q3), (q1,q3)
          dan (q4,q5).
          dapat diartikan q0,q1,q3 saling indistingushable dan q4 indistinguishable dengan q5
     f)  DFA setelah direduksi sebagai berikut;