tailieunhanh - Lecture Theory of Automata: Lesson 42

Lecture Theory of Automata: Lesson 42. The main topics covered in this chapter include: row language, nonterminals defined from summary table, productions defined by rows, rules for defining productions, all possible productions of CFG for row language of the example under consideration, CFG corresponding to the given PDA, . | Recap lecture 41 Recap of PDA in conversion form example of PDA in conversion form joints of the machine new pictorial representation of PDA in conversion form summary table row sequence row language. Note As has already been discussed that the Row language is the language whose alphabet Row1 Row2 Row7 for the example under consideration so to determine the CFG of Row language the nonterminals of this CFG are introduced in the following form Net X Y Z where X and Y are joints and Z is any STACK character. Following is an example of Net X Y Z Example continued Z b a PP PH a PH b PP PP If the above is the path segment between two joints then the net STACK effect is same as POP Z. For a given PDA some sets of all possible sentences Net X Y Z are true while other are false. For this purpose every row of the summary table is examined whether the net effect of popping is exactly one letter. Example continued Consider the Row4 of the summary table developed for the PDA of the language a2nbn FROM TO READ POP PUSH ROW Where Where What What What Number READ1 HERE b a 4 The nonterminal corresponding to the above row may be written as Example continued Net READ1 HERE a . Row4 is a single Net row. Consider the following row from an arbitrary summary table FROM TO READ POP PUSH ROW Where Where What What What Number READ9 READ3 b b abb 11 Example continued which shows that Row11 is not Net style sentence because the trip from READ9 to READ3 does not pop one letter form the STACK while it adds two letters to the STACK. However Row11 can be concatenated with some other Net style sentences . Row11Net READ3 READ7 a Net READ7 READ1 b Net READ1 READ8 b Example continued Which gives the nonterminal Net READ9 READ8 b now the whole process can be written as Net READ9 READ8 b Row11Net READ3 READ7 a Net READ7 READ1 b Net READ1 READ8 b Which will be a production in the CFG of the corresponding row language. Example continued In general to create productions from rows of summary table

• Tự động hoá
• Lecture Theory of Automata
• Bài giảng Lý thuyết về tự động hóa
• Theory of Automata
• Row language
• Arbitrary summary table
• The corresponding row language
• Computer theory
• Theory of computation
• Solution of the task
• Polish notation
• Total language tree
• Null production
• Nullable production
• Theorem regarding CNF
• The START state
• Nondeterministic PDA
• Equivalent PDA
• PDA corresponding to CFG
• STACK alphabet
• Computer science
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• Parsing techniques
• Turing machine
• DELETE subprogram
• Kleene’s theorem
• NFA corresponding
• Concatenation of FAs
• Distinguishable strings
• Indistinguishable strings
• Recap theorem
• Moore machine
• Mealy machine
• Applications of complementing
• Equivalent machines
• Mealy machines
• Regular languages
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I
• Pumping lemma version II
• Myhill Nerode theorem
• Quotient of a language