Chapter18

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