Bài giảng Theory Of Automata - Lecture 24

1Recap lecture 23 Mealy machines in terms of sequential circuit 2Task Build a Mealy machine corresponding to the following sequential circuit NAND DELAY AND AND input outputA B 3Solution of the Task Sequential circuit gives the following relations, that help in finding the current state of the machine new B = old A new A = (input) NAND (old A AND old B) output = (input) AND (old B) The transition at the state q0 while reading the letter 0, can be determined, along with the corresponding output character as under new B = old A = 0 new A = (input) NAND (old A AND old B) = 0 NAND ( 0 AND 0) = 0 NAND 0 = 1 output = (input) AND (old B) = 0 AND 0 = 0 4Solution continued Thus after reading 0 at q0 new B is 0 and new A is 1 i.e.machine will be at state (1,0)  q2 and during this process it’s output character will be 0. The remaining action of this sequential circuit can be determined as shown by the following suggested transition table of the corresponding Mealy machine 5Solution continued The corresponding transition diagram may be as follows 1(0,1)q10(1,1)q3q3 (1,1) 0(1,1)q30(1,1)q3q2 (1,0) 1(1,0)q20(1,0)q2q1 (0,1) 0(1,0)q20(1,0)q2q0 (0,0) Inputting 1 State Output Inputting 0 State Output Old state 6Solution continued Note: It may be noted that if the string 00 is read at any state, it results ending in state q3. 0/0, 1/0 0/0, 1/0 1/1 1/10/0 0/0 q0 q2 q1 q3 7Solution continued Running the string 01101110 on the previous machine, the output string can be determined by the following table 01100100output q3q2q1q3q2q1q3q2q0States 01110110Input 8Regular languages As already been discussed earlier that any language that can be expressed by a RE is said to be regular language, so if L1 and L2 are regular languages then L1 + L2 , L1L2 and L1 are also regular languages. This fact can be proved by the following two methods 1) By Regular Expressions: As discussed earlier that if r1, r2 are regular expressions, corresponding to the languages L1 and L2 then the languages L1 + L2 , L1L2 and L1 generated by r1+ r2, r1r2 and r1 *, are also regular languages. * * 9Regular languages continued 2) By TGs: If L1 and L2 are regular languages then L1 and L2 can also be expressed by some REs as well and hence using Kleene’s theorem, L1 and L2 can also be expressed by some TGs. Following are the methods showing that there exist TGs corresponding to L1 + L2, L1L2 and L1 * 10 Regular languages continued If L1 and L2 are expressed by TG1 and TG2 then following may be a TG accepting L1 + L2 -1- n+ p- m+   TG1 TG2 11 Regular languages continued If L1 and L2 are expressed by the following TG1 and TG2 then following may be a TG accepting L1L2 1- TG1 n+ p- TG2 m+ 12 Regular languages continued also a TG accepting L1 may be as under 1- n+   1- n p m+  * TG1 TG2 TG1 13 Example Consider the following TGs Following may be a TG accepting L1+L2 ab,ba ab,ba 1 aa,bbaa,bb 2TG1 aaa,bbb a,ba,b q+p- TG2 14 Example continued also a TG accepting L1L2 may be ab,ba ab,ba 1 aa,bbaa,bb 2 aaa,bbb a,ba,b q+p-TG1 TG2 -   15 Example continued and a TG accepting L2 ab,ba ab,ba 1- aa,bbaa,bb 2 aaa,bbb a,ba,b q+TG1 TG2  * p 16 Example continued aaa,bbb a,ba,b q+p- TG2   17 Complement of a language Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L / . Note: To describe the complement of a language, it is very important to describe the alphabet of that language over which the language is defined. For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L Theorem: If L is a regular language then, Lc is also a regular language. 18 Proof of the theorem Proof: since L is a regular language, so by Kleene’s theorem, there exists an FA, say F, accepting the language L. Converting each of the final states of F to non-final states and old non-final states of F to final states. FA, thus, obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L. Which shows that the new FA accepts the language Lc. Hence using Kleene’s theorem Lc can be expressed by some RE. Thus Lc is regular. 19 Example Let L be the language over the alphabet Σ = {a, b}, consisting of only two words aba and abb, then the FA accepting L may be n- o a p b q+ a,b r b a a,ba,b 20 Example continued Converting final states to non-final states and old non-final states to final states, then FA accepting Lc may be n o+ a p+ b q a,b r+ b a a,ba,b 21 Theorem Statement: If L1 and L2 are two regular languages, then L1  L2 is also regular. Proof: Using De-Morgan's law for sets (L1 c U L2 c)c = (L1 c)c  (L2 c)c = L1L2 Since L1 and L2 are regular languages, so are L1 c and L2 c. L1 c and L2 c being regular provide that L1 c U L2 c is also regular language and so (L1 c U L2 c)c = L1L2, being complement of regular language is regular language. 22 Summing Up Regular languages, complement of a language, theorem, proof, example, intersection of two regular languages