tailieunhanh - Lecture Theory of Automata: Lesson 35

Lecture Theory of Automata: Lesson 35. The main topics covered in this chapter include: examples of building TG’s corresponding to the regular grammar, null productions with examples, nullable productions with examples, unit production with example, chomsky normal form (definition), . | Recap Lecture 34 Example of Ambiguous Grammar Example of Unambiguous Grammer PALINDROME Total Language tree with examples Finite and infinite trees Regular Grammar FA to CFG Semi word and Word Theorem Defining Regular Grammar Method to build TG for Regular Grammar Example Consider the following CFG S aA bB A aS a B bS b then the corresponding TG will be A a a a S b b b B The corresponding RE may be aa bb . Following is another example Example Consider the following CFG S aaS bbS abX baX X aaX bbX abS baS then the corresponding TG will be aa bb aa bb ab ba X S ab ba The corresponding language is EVEN EVEN. Null Production Definition The production of the form nonterminal is said to be null production. Example Consider the following CFG S aA bB A aa B aS Here S and A are null productions. Following is a note regarding the null productions Note If a CFG has a null production then it is possible to construct another CFG without null production accepting the same language with the exception of the word . if the language contains the word then the new language cannot have the word . Following is a method to construct a CFG without null production for a given CFG Null Production continued Method Delete all the Null productions and add new productions . consider the following productions of a certain CFG X aNbNa N delete the production N and using the production X aNbNa add the following new productions X aNba X abNa and X aba Thus the new CFG will contain the following productions X aNba abNa aba aNbNa Note It is to be noted that X aNbNa will still be included in the new CFG. Nullable Production Definition A production is called nullable production if it is of the form N or there is a derivation that starts at N and leads to . N1 N2 N2 N3 N3 N4 Nn where N N1 N2 Nn are non terminals. Following is an example Example Consider the following CFG S AA bB A aa B B aS Here S AA and A B are nullable productions while B is null a production. Following is an example .