Context Free Grammars

Return to List of Lectures

Previous Lecture

• Misc
  • Colloquium
    • “Controllability of Graphs”
    • Dr. Cesar Aguilar, California State University Bakersfield
    • Monday (Feb. 22), 4:00 PM, Newton 201
    • Extra credit for short write-ups on how you connect the talk to other courses, interests, etc.
• Questions?
• Context Free Languages
  • Section 2.1
    • Stronger (i.e., more expressive) than regular languages?
      • Yes, can do 0ⁿ1ⁿ, balanced parentheses, arithmetic expressions, etc.
      • Strictly more expressive in fact: can create CFG for every regular language
    • Context free grammar
    • Formal definition: context free grammar = (V,Σ,R,S)
      • V = variables
      • Σ = terminals
      • R = rules, map variables to strings of variables/terminals
      • S = start variable
    • To generate a string in CFG’s language:
      • Start with S
      • Replace variables with right-hand sides of rules
      • Keep going recursively to eliminate all variables
    • Ambiguity is bad why?
      • Structure of a string sometimes implies meaning; having 2 different structures would be very bad
        
  • Examples
    • a* (list of 0 or more as)
      • Grammar 1
        • S → ε
        • S → aS
      • Generate a string
        • S
        • ⇒ aS
        • ⇒ aaS
        • ⇒ aaε = aa
      • Grammar 2
        • S → a
        • S → ε
        • S → SS
      • Generate aaa with 2 different leftmost derivations
        • S ⇒ SS ⇒ SSS ⇒ aSS ⇒ aaS ⇒ aaa
        • S ⇒ SS ⇒ aS ⇒ aSS ⇒ aaS ⇒ aaa
        • Ambiguous! And the ambiguity implies different structures for the string
          
    • Postfix expressions w/ 1-digit numbers and operators +, *
      • e.g., 23*, 13+45*+, 123456+++++, 4
      • Grammar
        • S → SSA
        • S → D
        • D → 0 | 1 | 2 | … | 9
        • A → + | *
  • Prove that the set of context free languages is closed under concatenation
    • L₁ = L( (V₁,Σ,R₁,S₁) ), L₂ = L( (V₂,Σ,R₂,S₂)
    • L₁L₂ = L( (V₁∪V₂, Σ, R₁∪R₂∪{S₀→S₁S₂}, S₀) )
• Next
  • Pushdown automata
  • Read section 2.2 through “Examples of Pushdown Automata”
    • Middle of page 111 through end of 116

Next Lecture