TAILIEUCHUNG - Lecture Theory of Automata: Lesson 39

Lecture Theory of Automata: Lesson 39. The main topics covered in this chapter include: PDA corresponding to CFG, examples of PDA corresponding to CFG, corresponding to any CFG there exists a PDA accepting the language generated by the CFG, consider the word aab with its left most derivation, . | Recap lecture 38 Example of PDA with table for running a string Equivalent PDA PDA for EVEN EVEN Language. Non Derterministic PDA Example of Non Derterministic PDA for EVEN PALINDROME Definition of PUSH DOWN Automata Example of Non Derterministic PDA for S S S S S 4 with table for running running the string 4 4 4 Note for choice of paths at POP state keeping in view left most derivation PDA corresponding to CFG Theorem Corresponding to any CFG there exists a PDA accepting the language generated by the CFG. Since an algorithm has already been discussed to convert the CFG in CNF so the PDA can be constructed corresponding to the CFG. As the CFG in CNF generates all the nonnull words of the corresponding CFL so accepting the null string if it is contained in the CFL can be managed separately. Following is an example in this regard Example Consider the following CFG which is in CNF and does not generate the null string S SB AB A CC B b C a The corresponding PDA will be a b RD1 RD2 AT ST C B PH S PP RD3 S A S PH B PH B PH C PH S PH A PH C Example continued Here the STACK alphabet S A B C where the TAPE alphabet a b Note It may be noted that when the POP state is entered either a nonterminal is replaced by two nonterminals at the top of the STACK accommodating a production or a nonterminal is popped out from the top of the stack and a READ state is entered to read a specified letter from the TAPE or else the machine crashes. Example continued The choice of path taken at POP state to accommodate the word belonging to the CFL can be determined by the left most derivation of the word. Consider the word aab with its left most derivation as follows Example continued Working String Generation Production Used S AB S AB step 1 CCB A CC step 2 aCB C a step 3 aaB C a step 4 aab B b step 5 Example continued First of all the START state is entered STACK TAPE aab The PUSH S state is entered STACK TAPE S aab Example continued The POP state is entered and to accommodate the production

• Tự động hoá
• Lecture Theory of Automata
• Bài giảng Lý thuyết về tự động hóa
• Theory of Automata
• PDA corresponding to CFG
• POP state to accommodate
• Working string generation
• 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
• 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