Automata

Automata ch6.

transitionCondition for AcceptAll the input is consumedThe last state is a final state\+) do not care stackWe will convert any context-free grammar G

CFL인지 확인하는 증명UnionConcatenationStar ClosureNot AllowedIntersectionComplementL1 = Context FreeL2 = RegularL1 intersection L2 = Context Free

다른 Machine처럼 accepter 역할도 하지만, 함수역할의 transducer도 수행Encoding이 필요하다digital computer가 할 수 있는 일은 TM이 모두 할 수 있다.TM with stayTM with multiple track tapesemi

exampleLHS의 제한 XTM = r.e. languages = unrestricted G

Halting Problem