tailieunhanh - Lecture Theory of automata - Lecture 43

This chapter presents the following content: Non-context-free language, pumping lemma for CFLs, 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 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 Non-Context-Free language There arises a question, whether all languages are CFL ? The answer is no. Non CFL: Languages which are not Context-Free, are called Non-CFL. To prove the claim that all languages are not Context-Free, the study of machines of word production from the grammar is needed Live production: A production of the form nonterminal string of two nonterminals is called a live production. Dead production: A production of the form nonterminal terminal is called a dead production. It may be noted that every CFG in CNF has only these types of productions. Following is a theorem Theorem: If a CFG is in CNF and if there is restriction to use the live production at most once each, then only the finite many words | Recap 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 Non-Context-Free language There arises a question, whether all languages are CFL ? The answer is no. Non CFL: Languages which are not Context-Free, are called Non-CFL. To prove the claim that all languages are not Context-Free, the study of machines of word production from the grammar is needed Live production: A production of the form nonterminal string of two nonterminals is called a live production. Dead production: A production of the form nonterminal terminal is called a dead production. It may be noted that every CFG in CNF has only these types of productions. Following is a theorem Theorem: If a CFG is in CNF and if there is restriction to use the live production at most once each, then only the finite many words can be generated. It may be noted that every time a live production is applied during the derivation of a word it increases the number of nonterminals by one. Similarly applying dead production decreases the nonterminals by one. Which shows that to generate a word, one more dead production are applied than the live productions . S XY aY aa Here one live and two dead productions are used In general, if a CFG in CNF has p live and q dead productions then all words generated without repeating any live production have at most (p+1) letters Theorem: If a CFG is in CNF with p live and q dead productions and if w is word generated by the CFG, having more than 2p letters then any derivation tree for w has a nonterminal z which is used twice, where the second z is the descended from the first z. It can be observed from the above theorem that generation tree of word w has more than p rows. Self-embedded nonterminal: A nonterminal is said to be self-embedded, if in a given .