공부한것들(주마다업뎃)/Computation theory

computation theory (6) - equivalence of CFG and PDA

개꾸리 2018. 9. 1. 15:52

    CFG와 PDA가 equivalence함을 보이기 위해서 CFL와 pushdown automata가 recognize하는 것이 필요충분조건임을 보이면 된다.

  1. Pushdown automata가 recognize하는 language는 context-free이다.
  2. Language가 context-free이면 pushdown automata가 recognize한다.
//증명추가


저작자표시 비영리