반응형 Computer Science/계산이론10 Halting Problem Halting Problem (정지 문제) Halting Problem은 튜링 머신의 계산이 종료 되는가? 에 대한 결정성 문제입니다. 이때, 결정성이란, 어떤 문제에 대한 계산의 결과가 단순히 예, 아니오가 될 때, 결정성을 갖는다고 정의됩니다. Turing Machine M과 입력 스트링 w가 주어졌을 때, q0w 에서 시작한 계산이 종료되는 가에 대한 판단 문제로, 다음 예시가 있습니다. ex) 튜링 머신 M과 입력스트링 w가 주어집니다. 이때, w는 무한히 주어지고, 어느 조건에 걸렸을 때 M이 종료됩니다. 그렇다면, 종료될 때 까지 무한히 계산할 텐데 이것을 M은 무한 루프로 판단하고 정지할것인지 말 것인지의 판단 문제가 있습니다. why ? 무한 루프로 판단하고 정지했는데, 바로 다음 입력스트.. 2023. 12. 27. 튜링 머신(Turing Machine) 이전에 사용했던 Pushdown Automata는 모든 정보를 Stack의 Top에서만 접근했기 때문에, 그 아래의 정보를 얻기 위해선 top이 가리키는 정보를 제거해야만 했습니다. 따라서, 그 과정에서 인식되지 않는 언어가 일부 발생합니다. ex) {a^n b^n c^n | n >= 0} 는 NPDA로 처리할 때, a를 스택에 push하고 a를 pop하며 b를 카운트합니다. 그리고, c를 처리할려고 할 때에는 스택이 empty이므로, 진행할 수 없습니다. 튜링 머신 (Turing Machine) 위 문제를 해결하기 위해, 튜링머신은 스택 대신 저장공간을 Tape로 사용합니다. Tape는 Cell로 구성된 무한 확장 가능한 1차원 배열의 형태를 띄고 있습니다. 각 셀은 하나의 문자를 저장할 수 있고, T.. 2023. 12. 27. 컴파일러 Compile Process 프로그래머가 작성한 코드는 컴파일러에 의해 어셈블리어, 기계어로 변환됩니다. 그 과정은 크게 다음과 같습니다. 소스 코드를 Scanner(Lexical Analyzer)를 통해 Token으로 변환 하고, Parser(Syntax Analyzer)를 통해 Abstract Syntax Tree(추상 구문 트리)를 생성합니다. 해당 추상 구문 트리를 Semantic Analyzer를 통해 Annotated Tree를 생성하고 Source Code Optimizer를 통해 최적화하여 Intermediate Code(중간 코드)를 만들어냅니다. 그리고 Code Generator는 생성된 중간 코드로 Target Code(Assembly Code)를 생성해냅니다. 위 과정을 천천히 분석.. 2023. 12. 27. Pushdown Automata 유한 오토마타의 경우, 입력 스트링이 왼쪽부터 오른쪽으로 소비되면서 처리되는데, 이 과정에서 앞에서 소비한 스트링의 개수를 확인할 수 없어서 앞의 스트링의 개수와 연관된 스트링이 있을 경우, 처리할 수 없습니다. ex) CFL L = {a^nb^n | n >= 0} 이를 해결하기 위해 오토마타에 스택 형태의 저장 기능을 가진 오토마타가 필요하게됩니다. Pushdown Automata Automata는 입력 스트링의 왼쪽 기호부터 처리하며 Stack의 top에 변화를 일으킵니다. 그리고 각 처리 단계에서 CU(Control Unit)의 상태를 변화 시키는데, 상태는 입력 기호와 스택의 top에 의해 결정됩니다. Nondeterministic Pushdown Automata (NPDA, 비결정적 Pushdo.. 2023. 12. 26. 이전 1 2 3 다음 반응형