Chapter 12 Context-Free Languages and Pushdown Automata.ppt

James L. Hein - Discrete Structures, Logic, and Computability Chapter 12: Context-Free Languages and Pushdown Automata Section 12.4 Context-Free Language Topics Remove Λ-productions Algorithm. Remove Λ-productions from grammars for langauges without Λ. 1. Find nonterminals that derive Λ. 2. For each production A → w construct all productions A → w’ where w’ is obtained from w by removing one or more occurrences of the nonterminals from Step 1. 3. Combine the original productions with those of step 2 and eliminate any Λ-productions. Example Remove Λ-productions from the grammar S → ABc A → aA | Λ B → bB | Λ. Solution. Step 1: The nonterminals A and B derive Λ. Step 2: From the production S → ABc we construct S → Bc | Ac | c. From the production A → aA we construct A → a. From the production B → bB we construct B → b. Step 3: S → ABc | Bc | Ac | c A → aA | a B → bB | b. Quiz Remove Λ -productions from S → ABc | Ab | c A → ABa | Λ B → Bbc | Λ. Solution. S → ABc | Ab | c| Bc | Ac | b A → ABa | Ba | Aa | a B → Bbc | bc. Chomsky Normal Form Productions have one of the following forms A → b (b a terminal) A → BC S → Λ (if Λ is in the language). Advantages: Parse trees are binary, which are easy to represent. Any string of length n 0 can be derived in 2n – 1 steps. Transform context-free grammar to Chomsky normal form Algorithm. Transform context-free grammar to Chomsky normal form 1. Remove A → Λ (if A ≠ S) by previous algorithm. (If S → Λ is removed, add it back.) 2. Remove unit productions (i.e., A → B): If A → B or A + B, then construct productions A → w where B → w is not a unit production. Now remove all unit productions. 3. For each production whose right side has two or more symbols, replace all occurrences of each terminal a with a new nonterminal A and also add the new production A → a. 4. Replace each production B → C1…Cn with n 2 with B → C1D where D → C2 …Cn. Repeat this step until all right sides have length two. Example Construct a C