Lecture 21 (More Decidability), 4/10/06

Concepts, definitions (in italics):

• An algorithm for deciding if a given CFG generates a given string.
• The languages A-CFG, A-PDA are decideable.
• An algorithm for deciding if a given CFG generates an empty language (i.e. no strings).
• The languages E-CFG, E-PDA are decideable.
• Given DFAs M1 and M2, an algorithm for creating a DFA M3 whose language is the difference of L(M1) and L(M2).
• The languages EQ-DFA, EQ-NFA, EQ-REX are decideable.
• Definition: The complement of a language
• Theorem: if L is decidable, then its complement is also decidable.
• Theorem: L is decidable if and only if both L and its complement are recognizable
• Definition: L is co-recognizable = its complement is recognizable
• Draw the Venn diagram for recognizable, decidable, and co-recognizable languages, and place A_TM there.
• Corollary: If L is recognizable but not decidable, then its complement is not recognizable.
• A_TM is recognizable (build a recognizer that simulates)

Reading:

• Finish chapter 4.1, except for Theorem 4.9

Skills:

• Know new definitions, understand new concepts.
• Understand proofs of all the results above (the first is being done as homework).
• Understand how to enumerate all derivations of a given length for a given CFG.
• Understand the algorithms for deciding all the decidable languages listed above.
• Understand the algorithm for recognizing A_TM.

Notes:

• A CFG in Chomsky Normal form has a derivation of length 2k-1 for a string of length k > 0.

• Algorithm for E_CFG:
  1) (Init) For every rule with no variables on RHS, mark variable on LHS.
  2) (Loop) For every rule with no unmarked variables on RHS, mark variable on LHS.
  3) Repeat step 2 until we cannot mark any more variables.
  4) If start variable is marked, return NO; else return YES.
  

• EQ_DFA = { (<A> , <B>) : A, B are equivalent DFA's }
  EQ_NFA = { (<A> , <B>) : A, B are equivalent NFA's }
  EQ_REX = { (X,Y) : X, Y are equivalent regular expressions}
  They are all decidable
• The algorithm for deciding EQ_DFA relies on the following facts for any sets S1 and S2
  • S1 = S2 iff both S1 - S2 and S2 - S1 are empty.

• EQDFA-decider does the following on input (A,B)

  1) syntax check, reject if fails
  2) C = construct the description of DFA accepting L(A) – L(B)
  3) D = construct the description of DFA accepting L(B) – L(A)
  4) Run EDFA decider on C, then on D
  5) If both are yes (i.e. they both have empty languages), return accept; else reject

• The language EQ-CFG is not decidable (we have not yet proved it!)