Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Theory of automata - Lecture 35

The main contents of this chapter include all of the following: 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 The corresponding RE may be (aa+bb)+. Following is another example a S- A B a a b b b + Example Consider the following CFG S aaS|bbS|abX|baX| X aaX|bbX|abS|baS, then the corresponding TG will be The corresponding language is EVEN-EVEN. ab,ba S- ab,ba aa,bb aa,bb X + 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 . | 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 The corresponding RE may be (aa+bb)+. Following is another example a S- A B a a b b b + Example Consider the following CFG S aaS|bbS|abX|baX| X aaX|bbX|abS|baS, then the corresponding TG will be The corresponding language is EVEN-EVEN. ab,ba S- ab,ba aa,bb aa,bb X + 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 i.e. 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 e.g. 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 i.e. N1 N2, N2 N3, N3 N4, , Nn , where N, N1, N2, , Nn are non terminals. Following is an example Example Consider the following .