Chapter18

75 %
25 %
Information about Chapter18
Entertainment

Published on September 19, 2007

Author: Pravez

Source: authorstream.com

CSI 3104 /Winter 2006: Introduction to Formal Languages Chapter 18: Decidability:  CSI 3104 /Winter 2006: Introduction to Formal Languages Chapter 18: Decidability Chapter 18: Decidability I. Theory of Automata  II. Theory of Formal Languages III. Theory of Turing Machines … Chapter 18: Decidability:  Chapter 18: Decidability Examples of undecidable problems: Are the languages generated by two context-free grammars the same language? Is a particular context-free grammar ambiguous? Given a context-free grammar that is ambiguous, is there another context-free grammar that generates the same language that is not ambiguous? More examples:  More examples Is the complement of a context-free language also context-free? Is the intersection of two context-free languages also context-free? Is the intersection of two context-free languages empty? Given a context-free grammar, are there any words that are not in the language generated by the grammar? Chapter 18: Decidability:  Chapter 18: Decidability Some Decidable Problems Given a context-free grammar, is the language that it generates empty? Emptiness problem. Given a context-free grammar, is the language that it generates finite or infinite? Finiteness problem. Given a context-free grammar and a word w, is w a word that can be generated by the grammar? Membership problem. Chapter 18: Decidability:  Chapter 18: Decidability Theorem: Given a context-free grammar, there is an algorithm to determine if the language it generates is empty. Proof. S  Λ? (by the constructive algorithm in Chapter 13 for deciding if a nonterminal is nullable) If not, convert the grammar to Chomsky normal form. Is there a production of the form: S  terminal? If not, repeat the steps: Choose a nonterminal N such that: N  t (sequence of terminals). Replace N on the right sides of productions with t. Remove all other productions for N. Stop if there is a production S  t or there are no more nonterminals to choose. Example 1:  Example 1 Example 1: SXY XAX XAA Aa YBY YBB Bb Step 1: replace all A’s by a, all B’s by b: SXY XaX Xaa YbY Ybb Step 1: Replace all X’s by aa and all Y’s by bb: S aabb Step 1: replace all S’s by aabb Step 2: terminate step 2, S has been eliminated. CFG produces at least one word. Example 2:  Example 2 XXY XAX Aa YBY YBB Bb Replace A by a, B by b: SXY XaX YbY Ybb Replace Y’s by bb: SXbb XaX Terminate step 1, S still there, CFG generates no word. Chapter 18: Decidability:  Chapter 18: Decidability An algorithm that can determine if a nonterminal X can generate a sequence of terminals Reverse S and X and use the algorithm from the previous theorem. If X cannot generate a sequence of terminals, X is unproductive. Chapter 18: Decidability:  Chapter 18: Decidability Theorem: There is an algorithm to decide whether or not a given nonterminal X in a context-free grammar can ever be used in generating words. Proof. Determine if X is unproductive. If not, Chapter 18: Decidability:  Chapter 18: Decidability Find all unproductive nonterminals. Remove all productions containing unproductive nonterminals. Paint all X’s blue (on the right and left in the grammar). If any nonterminal on the right of a production is blue, paint the nonterminal on the left blue. Then paint blue all occurrences of this nonterminal in the grammar. Repeat step 4 until no new nonterminals are painted blue. If S is blue, there is a derivation that uses X. If X cannot be used in a derivation, X is useless. Example 1:  Example 1 S  ABa | bAZ | b A  Xb | bZa B  bAA X  aZa | aaa ZZAbA X terminates, Z is useless (why?) A is blue, B is blue, S is blue A  Xb B  bAA A  aaab, B  bAaaab  bXbaaab S  Aba  aaabBa  aaabbXbaaaba X productive Example:  Example SEC EAC ABC Cc Bb A blue  EEC E blue  SEC S blue  A usefull Chapter 18: Decidability:  Chapter 18: Decidability An algorithm that can decide if a nonterminal X is self-embedded. Replace X’s on the left in productions with Ж. Paint all X’s blue, and use the blue paint algorithm (steps 3 to 5 of the previous algorithm). If Ж is blue, then X is self-embedded. Chapter 18: Decidability:  Chapter 18: Decidability Theorem: There is an algorithm to decide if a context-free grammar generates a language that is finite or infinite. Find all useless nonterminals. Test all nonterminals to see if any is self-embedded using the above algorithm. If step 2 found a self-embedded nonterminal, then the language is infinite. Otherwise it is finite. Example:  Example S  Aba | bAZ | b X aZa | bA | aaa AXb | bZa ZZAbA BbAA Z useless (it appears in all its own productions) S  Aba | b X bA | aaa AXb BbAA S  Aba | b Ж  bA | aaa AXb BbAA X blue; AXb  A blue; ЖbA  Ж blue; BA  B blue; SAba  S blue  Language generated by CFG is infinite Chapter 18: Decidability:  Chapter 18: Decidability Membership problem Given a context-free grammar G and a word w = w1w2…wn, is w a word that can be generated by the grammar? CYK Algorithm (Cocke, Kasami(1965),Younger(1967) Transform G into a Chomski Normal Form. At each step i of the algorithm, 1≤i≤n, find all sub words of w with length i that can be generated starting from any of the non terminals. Details … Parsing not covered

Add a comment

Related presentations

Related pages

Chapter 18 - Automate the Boring Stuff with Python

Chapter 18 – Controlling the Keyboard and Mouse with GUI Automation. Support the Author: Buy the book on Amazon or the book/ebook bundle directly from No ...
Read more

DAV Chapter 18 | DAV Chapter 18 of Carlton County

Welcome to Disabled American Veterans Chapter 18 of Carlton County Minnesota. The DAV is dedicated to the help of disabled veterans and veterans in our ...
Read more

Chapter 18 - The Reformation Online

Daimyo Nobunaga, sixteenth century military dictator of Japan, welcomed the Jesuit missionaries who came with the ...
Read more

Chapter 18. Syntax - Oracle

Chapter 18. Syntax This chapter presents a grammar for the Java programming language. The grammar presented piecemeal in the preceding chapters ...
Read more

Chapter18 - Answer - Scribd

CHAPTER18 18-1. PREPARATION OF AUDITED FINANCIAL STATEMENTS Salve Company Requirement (1) Salve Company <...
Read more

Test Bank - Chapter18 FS Analysis - scribd.com

Chapter 18 “How Well Am I Doing?” Financial Statement Analysis True/False 1. F Medium In determining whether a company's financial condition is
Read more

Indiana Ch-18 Homepage

ch-18 newsletter . mid-america regional info. ch-18 meeting information . newsletter archives . about ch-18
Read more

Chapter18: REDUCTIONOFADVERBCLAUSESTO ...

Chapter18: REDUCTIONOFADVERBCLAUSESTO MODIFYINGADVERBIALPHRASES ... 194 CHAPTER18,ReductionofAdverbClausestoModifyingAdverbialPhrases EXERCISE8,p.380.
Read more

Chapter 18: Sonification for Process Monitoring | The ...

by Paul Vickers. Description. This chapter looks at a range of auditory display and sonification applications that have tackled the problem of monitoring ...
Read more

Chapter 18 - Department of Physics at UF

Clicker question 1. A wire has resistance R. A second wire has twice the length, twice the diameter, and twice the resistivity of the first wire.
Read more