[계산이론] Pushdown Automata - 3
결정론적 푸시다운 오토마타
항상 움직임에서 선택지가 없는 푸시다운 오토마타
주어진 입력 심볼과 스택의 꼭대기에 대해서, 최대 한 번의 움직임만 가능합니다.
어떤 구성에서 𝜆-움직임이 가능한 경우, 입력을 소비하는 대안이 없습니다.
결정론적 푸시다운 오토마타 • 유한 오토마톤과의 차이점 ▪ DFA ❖ 𝜆-전이가 허용되지 않음 ❖ 죽은 상태가 없음 ❖ DFA는 표현 능력 측면에서 NFA와 동등함 ▪ DPDA ❖ 𝜆-전이가 가능함 • 스택의 맨 위가 다음 움직임을 결정하는 데 역할을 함 • 𝜆-전이의 존재는 비결정성을 의미하지 않음 ❖ 일부 DPDA의 전이는 빈 집합으로 이어질 수 있음 • 죽은 상태가 발생할 수 있음 • 결정성을 위한 유일한 기준은 항상 한 번의 가능한 움직임만 존재하는 것임 ❖ DPDA와 NPDA는 동등하지 않을 수 있음
• 𝛿 𝑞, 𝑎, 𝑏는 최대 한 요소를 포함합니다 (𝑞 ∈ 𝑄, 𝑎 ∈ Σ ∪ 𝜆 , 𝑏 ∈ Γ) • 만약 𝛿 𝑞, 𝜆, 𝑏가 비어 있지 않으면, 모든 𝑐 ∈ Σ에 대해 𝛿 𝑞, 𝑐, 𝑏는 비어 있어야 합니다.
• 만약 𝛿 𝑞, 𝜆, 𝑏가 비어 있지 않으면, 모든 𝑐 ∈ Σ에 대해 𝛿 𝑞, 𝑐, 𝑏는 비어 있어야 합니다.
𝛿 𝑞0, 𝑎, 𝑎 = { 𝑞0, 𝑎𝑎 } • 𝛿 𝑞0, 𝜆, 𝑎 = { 𝑞1, 𝑎 }
파싱 효율성 • 결정론적 컨텍스트-프리 언어의 중요성 ▪ 이들은 효율적으로 파싱될 수 있습니다. ❖ 오직 하나의 선택만 가능 • 어떤 문장의 가장 왼쪽 유도를 얻을 것으로 가정해 봅시다 ▪ 각 단계에서 어떤 생성 규칙을 적용할 것인지 결정할 수 있다면, 파싱의 효율성이 상당히 높아집니다.
LL 문법 ▪ 주요 특징 ❖ 입력의 제한된 부분을 살펴보면 어떤 생성 규칙을 사용해야 하는지 예측할 수 있습니다. ▪ 첫 번째 L은 입력이 왼쪽에서 오른쪽으로 스캔된다는 것을 나타냅니다. ▪ 두 번째 L은 가장 왼쪽 유도가 구성된다는 것을 나타냅니다.
어떤 생성 규칙을 적용할지 결정하려면 주어진 입력 문자열의 처음 두 개의 기호를 검사합니다. ▪ 두 번째 기호가 '𝑏'이면, 우리는 𝑆 → 𝑎𝑏를 적용해야 합니다. ▪ 두 번째 기호가 '𝑎'이면, 우리는 𝑆 → 𝑎𝑆를 적용해야 합니다.
▪ 문법이 현재 스캔된 기호와 다음 k-1개 기호의 "look ahead"를 통해 올바른 생성 규칙을 고유하게 식별할 수 있다면 해당 문법은 LL(k) 문법입니다. ▪ 이것은 LL(2) 문법의 예입니다.
이것은 LL 문법이 아닙니다! ▪ 첫 번째 기호가 '𝑎'인 경우에도 어떤 규칙을 사용해야 하는지 알 수 없습니다, 𝑆 → 𝑆𝑆 또는 𝑆 → 𝑎𝑆𝑏 ▪ 심지어 처음 두 개의 기호를 보더라도... ❖ 𝑎𝑎𝑏𝑏 𝑎𝑎𝑏𝑏𝑎𝑏 ❖ 어떤 규칙을 사용해야 하는지 알 수 없습니다, 𝑆 → 𝑆𝑆 또는 𝑆 → 𝑎𝑆�
▪ 하지만 우리는 원래 문법과 동등한 LL 문법을 생성할 수 있습니다. ❖ 𝑆′ → 𝑎𝑆𝑏𝑆 ❖ 𝑆 → 𝑎𝑆𝑏𝑆 | 𝜆 ▪ LL 문법에 대한 더 자세한 내용은 컴파일러 수업에서 소개될 예정입니다! (희망적으로..)