Disclaimer: The following are my incomplete jot-notes for the CS 360 final exam. There is a possibility of errors.

Context Free Grammar (CFG), G = (v, ∑, S, P)

• Every regular language is a CFL
• Language L is a CFL if there is a CFG s.t. L = L(G)
• Chomsky Normal Form: A-> BC & A->a
• For any G, there is G’ s.t. L(G’) = L(G) - {L }
• Ambiguous grammar: 2 different left-most derivations for some w Є L(G)

Pushdown Automaton (PDA), M = (Q, ∑, Γ, q0, Z0, A, δ)

• PDA = FA + Stack
• Transitions: δ(q, a, x) = (p, α)
• Arcs on diagrams: input symbol, top stack symbol/new top symbol(s)
• q = current state; a = input (string); x = stack symbol; p = new state; α = new stack symbol
• NFA-L or FA is a PDA whose stack contents are never changed
• L is a DCFL if there is a DPDA, M, accepting L i.e. L(M) = L
• DCFL is always a CFL
• CFL ≠ DCFL, CFL NOT always a DCFL
• Language accepted by PDA are CFLs
• For any NFA, there is a FA recognizing same lang. This is not true for PDA i.e. NPDA≠DPDA
• Not every language accepted by a PDA can be accepted by a DPDA
  eg. PAL (palindromes) not accepted by a DPDA
• Every CFL can be recognized by some non-determinstic PDA
  For CFG, G, & PDA, M. L(M) = L(G)
• CFG -> PDA via empty stack
• Acceptance
  - Final state: accepting configuration does NOT depend on stack contents
  - Empty stack: accepted if PDA reaches configuration where stack is empty

Closure Properties

° L1 & L2 are CFLs => L1 U L2, L1L2, L1* are CFL

Home 

Page updated on: 19-Feb-2002 03:40 PM