Question

Figure 4/ Rajah 4 (20/100) (e) Consider the machine Moore M shown in Figure 5. The state So is the starting state and state S2 is the terminal state. The input set is I {a, b}. Pertimbangkan mesin Moore M ditunjukkan dalam Rajah 5. Keadaan So adalah keadaan mula dan keadaan S2 adalah keadaan terminal. Set input adalah | = (a, b) 8-8-8 So Figure 5: Machine Moore M/ Rajah 5: Mesin Moore M (i) What is L(M)? Apakah L(M)? (ii) Construct a grammar G such that L(G) = L(M). Bina tatabahasa G supaya L(G) = L(M). 10 [CPT112] - 10 (il Find a regular expression over input set I {a, b} that corresponds to L(M) Cari ungkapan biasa ke atas set input I = fa, b} yang sepadan dengan L(M) (iv) Give one (1) example each of strings can be accepted and rejected based on L(M) Beri satu (1) contoh setiap rentetan boleh diterima dan ditolak berdasarkan L(M) (24/100)

Answer 1

Answer:

i) If you see the strings accepted by this machine they have at least two b's in them.

{bb,abb, bab,bba,bbb, aabb, baab, bbaa,bbab,bbba,bbbb......}

This machine accepts all the string which have at least two b's in them. So this is machine which accepts at least two b's.

ii) The Grammar for this language can be written as,

SAbAbC AAa/e CCa/Cb/e

iii) The Regular expression corresponding to this machine is given by,

1) At state S0 we can have any numbers of a so

a

2) One b at state S1 and then any no of a so

ba

3) At S2 one b and then any number of a or b so

bα+01

So the regular expression representing this machine is

aba b(ab)

iv) The strings accepted by this machine are as follows:

  {bb,abb, bab,bba,bbb, aabb, baab, bbaa,bbab,bbba,bbbb......}

and the string rejected by this machine are {a,b,ab,ba} any string which have less than 2 b's in them