6. 형식 언어와 오토마타 [핵심, 응용]

이 파트에서는 순수하게 형식 언어 및 오토마타 과목에서 물어볼 수 있는 질문을 나열한다.

(컴파일러 과목은 제외한다는 의미입니다)

 

이 파트는 기출을 포함하지 않는다. 그 이유는 KAIST 기출문제가 이론 질문보다는 수학적으로 또는 주어진 Grammar을 갖고 푸는 문제이기 때문이다. 굳이 이론 질문을 뽑는다면 촘스키 위계(Chomsky Hierarchy)를 외워가는 것을 추천한다.

 

* 참고 교재: Introduction to the Theory of Computation (Michael Sipser)

 

[핵심편]

Q. Finite Automata란 무엇인가? Language란 무엇인가? Regular Language란 무엇인가?

 

Q. DFA와 NFA가 무엇인지 설명하라.

 

Q. DFA의 Formal Definition, Accept의 의미를 설명하라.

 

Q. NFA의 Formal Definition을 설명하라.

 

Q. NFA 집합과 Regular Language는 같은 집합인가? 그 이유를 설명하라. NFA를 DFA로 바꾸는 방법을 함께 설명하라.

 

Q. GNFA를 설명하라. GNFA를 Regular expression으로 바꾸는 방법을 설명하라.

 

Q. 어떤 Language가 Non-regular한다는 것을 어떻게 보일 것인가?

 

Q. CFG, CFL은 무엇인가? Regular Language와의 관계는?

 

Q. Regular Language가 CFL에 속함을 설명하라.

 

Q. Chomsky Normal Form에 대해 설명하라. Form으로 바꾸는 과정을 설명하라.

 

Q. 스트링 w가 Chomsky-Form으로 된 CFL로 만들어질 수 있는지 확인하는 DP 알고리즘을 설명하라. 이의 Complexity는?

 

Q. PDA(Push Down Automata)란 무엇인가? PDA 집합과 CFL은 같은 집합인가?

 

Q. CFG의 Formal Definition을 설명하라.

 

Q. CFL의 Pumping Lemma을 설명하라.

 

Q. Turing Machine은 무엇인가? DFA와의 차이점은? Formal Definition은 무엇인가?

 

Q. STM, Non-deterministic TM, Multitape TM는 어떤 특성을 갖는가? 뒤 두 TM의 Complexity를 STM과 비교하라.

 

Q. Turing Recognizable, Turing Decidable이란 무엇인가? P, NP, NP-Complete, TR, TD의 집합 관계를 말해보라.

 

[응용편]

Q. Regular Language는 Regular operation, Complement, Intersection에 닫혀있음을 설명하라.

 

Q. Multitape TM은 STM으로 바꿀 수 있는가? Non-deterministic TM은 Deterministic TM으로 바꿀 수 있는가?