tailieunhanh - Lecture note Theory of automata - Lecture 17

Lecture Theory of automata - Lecture 17 includes the following content: Converting NFA to FA (method 3), example, NFA and Kleene’s theorem method 1, examples, NFA and Kleene’s theorem method 2 , NFA corresponding to union of FAs, example. | Lecture note Theory of automata - Lecture 17 Lecture 26 Theory Of Automata By Dr. MM Alam 1 Lecture 25 Summary Regular Grammar conversion to FA JFLAP Practical demonstration Elimination of NULL Productions Elimination of UNIT Productions 2 Eliminate Unit Productions EXAMPLE Consider S A Ibb A B Ib B S a Separate the units from the nonunits . Unit Production Other ones S A S bb 3 A B A b Killing Unit Productions S A Ibb A B Ib B S a S A gives S b S A B gives S a A B gives A a A B S gives A bb B S gives B bb 4 Introduction to Chomsky Normal form If L is a language generated by some CFG then there is another CFG that generates all the non-ʎ words of L all of whose productions are of one of two basic forms string of only Nonterminals or Nonterminal - one terminal 5 Introduction to Chomsky Normal form Example 1 Let start with the CFG S X I X2aX2 aSb I b Xl X2X2 I b X2 aX2 I aaX1 After the conversion we have S X1 X1 X 2X 2 S X2AX 2 X1 B S ASB X2 AX 2 6 S B X2 AAX1 Introduction to Chomsky Normal form Example 1 We have not employed the disjunction slash I but instead have written out all the productions separately so that we may observe eight of the form Nonterminal string of Nonterminals and two of the form Nonterminal one terminal 7 Introduction to Chomsky Normal form EXAMPLE 2 Why not simply replace all a s in long strings by this Nonterminal For instance why cannot S Na N alb become S NN N a lb What do you think 8 EXAMPLE 2 The answer is that bb is not generated by the first grammar but it is by the second. The correct modified form is S NA N alb A a 9 Introduction to Chomsky Normal form EXAMPLE 3 The CFG S XY X XX Y YY Y a Y b which generates aa bb 10 Introduction to Chomsky Normal form EXAMPLE 3 With our algorithm become S XY X XX y yy X A Y B A a B b 11 Introduction to Chomsky Normal form EXAMPLE With our algorithm become S XY X XX Y yy X A Y B A a Needless Unit Productions wastage of time B b 12 What is Chomsky Normal form Definition If a CFG has .