menu

Lecture 11 • 2017/10/12
  • Chomsky Normal Form
    • Context-free grammar notation for which every rule is of the form A → BC or A → ε
      • B and C must not be start variables
  • Any context-free language is generated by a context-free grammar in Chomsky normal form
    • Start by creating start variable S0 pointing to S, the first variable in the string (this avoids start variable of CFG from appearing on RHS)
    • Remove all A → ε rules where A is not start variable
      • This will change rules R → A to R → ε, which will be processed later
      • S → ASA would become S → ASA | SA | AS | S
    • Remove all unit rules such as A → B
    • Convert seqeunce rules A → u1u2…uk (where k ≥ 2) to a series of rules A → u1A1, A1 → u2A2 etc, where each Ai is a new variable
  • Pushdown Automata (stack type)
  • Has alphabets – one for the inputs (lowercase) & one for the stack (uppercase)
    • In most cases, the stack alphabet will be larger than that of the inputs
    • b,B → A means that if input is b & stack top has B, digest b and replace top stack with A
      • b,ε A means to push A to stack if input is b (popping ε, which is nothing)
    • Note that stack usage means that we can only see the top item of the stack. There is no notion of moving through the stack
Lecture 12 • 2017/10/17
  • Gave more examples on PDA
  • Theorem – a language is context free iff some PDA recognizes it
  • CFG to PDA
    • Place marker symbol $ & start variable on stack
    • Repeat following forever
      • If top stack is A, nondeterministically select one of rules for A & substitute
      • If top stack is terminal symbol α read next symbol from input & compare to α. If match, repeat, otherwise reject
      • If top stack is symbol $, enter accept state. This will accept the input if it has been completely read
Lecture 13 • 2017/10/19
  • If x can bring P from p with empty stack to q with empty stack, Apq generates x
    • If computation has 0 steps, x is already the empty string
    • Induction - assume true for length k, prove for k + 1
      • Once that stack is non empty, it will become empty either at the very last step of at some intermediate point
        • If never happened in between, symbol p i pushed at the first move and popped at the last step
          • For any portion y = azb, with y transitioning from empty state to empty state, we may do the same for z without the need of passing through transitions a and b (given that there does not exist an empty state in between)
        • If empty state exists in between, transitions can be split by the empty states. Note that the sum of those transitions must be less than the total number of steps, as it requires at least two steps to pop into an empty state and push back into a nonempty state
    • Pumping Lemma for CFLs
      • One way only; not iff
      • A context-free language L must have a number p where, if s is any string in L of length ≥ p, s may be divided into uvxyz such that:
        • for each i ≥ 0, uvixyiz ∈ A
        • |vy| > 0
        • |vxy| ≤ p