效绵鼎 Summary of Decision Properties As usual,.when we talk about“aCFL” we really mean "a representation for the CFL,e.g., a CFG or a PDA accepting by final state or empty stack. There are algorithms to decide if: 1.String w is in CFL L 2. CFL L is empty. 3. CFL L is infinite ,16
Summary of Decision Properties ◼ As usual, when we talk about “a CFL” we really mean “a representation for the CFL, e.g., a CFG or a PDA accepting by final state or empty stack. ◼ There are algorithms to decide if: 1. String w is in CFL L. 2. CFL L is empty. 3. CFL L is infinite. 16
效绵鼎 Non-Decision Properties Many questions that can be decided for regular sets cannot be decided for CFL's. Example:Are two CFL's the same? Example:Are two CFL's disjoint? o How would you do that for regular languages? Need theory of Turing machines and decidability to prove no algorithm exists. .17
Non-Decision Properties ◼ Many questions that can be decided for regular sets cannot be decided for CFL’s. ◼ Example: Are two CFL’s the same? ◼ Example: Are two CFL’s disjoint? How would you do that for regular languages? ◼ Need theory of Turing machines and decidability to prove no algorithm exists. 17
效绵鼎 Testing Emptiness We already did this. We learned to eliminate useless variables If the start symbol is one of these,then the CFL is empty;otherwise not. .18
Testing Emptiness ◼ We already did this. ◼ We learned to eliminate useless variables. ◼ If the start symbol is one of these, then the CFL is empty; otherwise not. 18