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 # 26 Theory Of Automata By Dr. MM Alam 1 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 A → B A → b B → S B → a 3 Killing Unit Productions 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 B → S → A gives B → b 4 S → A Ibb A → B Ib B → S | a 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 | Lecture # 26 Theory Of Automata By Dr. MM Alam 1 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 A → B A → b B → S B → a 3 Killing Unit Productions 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 B → S → A gives B → b 4 S → A Ibb A → B Ib B → S | a 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 S → B X2 → AAX1 A → a B → b 6 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 l b 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, .