tailieunhanh - Lecture Theory of automata - Lecture 42

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 PH a PP PP Z PH b b PP a 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 . | 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 PH a PP PP Z PH b b PP a 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} The nonterminal corresponding to the above row may be written as 4 -- a b HERE READ1 ROW Number PUSH What POP What READ What TO Where FROM Where Example continued Net (READ1, HERE, a) . Row4 is a single Net row. Consider the following row from an arbitrary summary table 11 abb b b READ3 READ9 ROW Number PUSH What POP What READ What TO Where FROM Where 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. .