Push Down Automata

7.1 NPDA

• transition

• Condition for Accept

1. All the input is consumed
2. The last state is a final state
   +) do not care stack

7.2 PDA & CFL

Convert CFL to NPDAs

• We will convert any context-free grammar G (CFL)
• to an NPDA automaton M (NPDA)

6장에서 설명한 GNF에서 하나의 symbol과 여러개의 Variables
--> G를 읽어나가면서 Symbol의 증가
--> get String (with Stack = progress)

7.3 DPDA

Not Allowed!!

1. 같은 input에 여러 state
2. λ도 읽고 일반 input도 읽기

NPDAs has powerful than DPDAs

L을 체크해보면 중간지점을 찾아야 Reverse String을 내보내는데 State가 확정 불가 == DPDA 불가