TAILIEUCHUNG - Lecture Theory of automata - Lecture 44

In this chapter, the following content will be discussed: Decidability, whether a CFG generates certain string (emptiness), examples, whether a nonterminal is used in the derivation of some word (uselessness), examples, whether a CFL is finite (finiteness), example, whether the given string is generated by the given CFG (membership), example, parsing techniques, top down parsing, example. | Decidablity Following are the decidable problems . CFG Whether or not the given CFG generates any word? Problem of emptiness of CFL. Whether or not the given CFG generates the finite language? Problem of finiteness. Whether or not the given string w can be generated by the given CFG? Problem of membership. Following are algorithms showing that the answers to the above three questions are yes. Algorithm 1 (Emptiness): If the given CFG contains a production of the form S , then obviously the corresponding CFL is not empty. If the CFG contains the production of the form S t, where t is a terminal or string of terminal then t is a word of the corresponding CFL and CFL is not empty. If the CFG contains no such production then For each nonterminal N with N t, pick one production for N (if there are more than one) and replace N by t in the right side of each production wherever it lies. Remove all such productions from the CFG. Doing so the CFG will be changed, it will generate atleast

• Kỹ thuật lập trình
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Computer science
• Parsing techniques
• Automata theory
• Automata theory languages
• Automata theory computation
• Pushdown automata
• Context Free grammars
• Regular languages
• Additional classes
• Intractable problems
• Properties of context free languages
• 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
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• 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
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I