tailieunhanh - Lecture Theory of Automata: Lesson 43

Lecture Theory of Automata: Lesson 43. The main topics covered in this chapter include: non-context-free language, live production and dead production, self-embedded nonterminal, pumping lemma for CFLs, the pumping lemma discussed for infinite regular language L, . | 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 1 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 2 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 3 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. 4 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 5 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. 6 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 derivation of a word it ever occurs as a tree .

• Tự động hoá
• Lecture Theory of Automata
• Bài giảng Lý thuyết về tự động hóa
• Theory of Automata
• Non context free language
• Self embedded nonterminal
• Pumping lemma for CFLs
• 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
• 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