[계산이론] Pushdown Automata - 2

Review: Pushdown Automata

• 하나의 전이에서 여러 개의 스택 알파벳을 푸시하거나 팝할 수 있나요?
  • 네
•  하나의 전이에서 동시에 푸시하거나 팝할 수 있나요?
  • 네
• 여러 개의 푸시/팝 작업을 수행하는 nPDA가 주어졌을 때, 하나의 전이에서 하나의 기호를 푸시/팝하는 동등한 nPDA를 생성할 수 있나요?
  • 네

---

CFG to PDA

• 주어진 CFG로부터 nPDA 생성
  • 가정
    • CFG가 GNF(Greibach Normal Form) 형식임
    • 문자열의 왼쪽 최하위 파생을 고려
  •  기본 아이디어
    • 우측 항의 변수 → 스택
    • 우측 항의 터미널 → 입력

---

• 주어진 CFG로부터 nPDA 생성
  • 단계 (1) 시작 기호 → 스택
  • 단계 (2) ∀𝐴 → 𝑎𝑥
    • 스택: 𝐴 → 𝑥
    • 입력: 𝑎 → 𝜆

---

• 주어진 CFG로부터 nPDA 생성
  • 예시: 𝑆 → 𝑎𝑆𝑏𝑏 | 𝑎
    • (1) GNF로 변환: 𝑆 → 𝑎𝑆𝐴 | 𝑎, 𝐴 → 𝑏𝐵, 𝐵 → 𝑏
    • (2) 𝛿 𝑞0, 𝜆, 𝑧 = 𝑞1, 𝑆𝑧           … 시작 기호 → 스택
    • (3) 𝛿 𝑞1, 𝑎, 𝑆 = 𝑞1, 𝑆𝐴 , 𝑞1, 𝜆          … ∀𝐴 → 𝑎𝑥, 스택: 𝐴 → 𝑥, 입력: 𝑎 → 𝜆
    • (4) 𝛿 𝑞1, 𝑏, 𝐴 = 𝑞1, 𝐵              … ∀𝐴 → 𝑎𝑥, 스택: 𝐴 → 𝑥, 입력: 𝑎 → 𝜆
    • (5) 𝛿 𝑞1, 𝑏, 𝐵 = 𝑞1, 𝜆                … ∀𝐴 → 𝑎𝑥, 스택: 𝐴 → 𝑥, 입력: 𝑎 → 𝜆
    • (6) 𝛿 𝑞1, 𝜆, 𝑧 = 𝑞2, 𝑧                   … 최종 상태

• Processing "𝑎𝑎𝑎𝑏𝑏𝑏𝑏"

(𝑞0, 𝑎𝑎𝑎𝑏𝑏𝑏𝑏, 𝑧)

⊢ (𝑞1, 𝑎𝑎𝑎𝑏𝑏𝑏𝑏, 𝑆𝑧) ⊢ (𝑞1, 𝑎𝑎𝑏𝑏𝑏𝑏, 𝑆𝐴𝑧)

⊢ (𝑞1, 𝑎𝑏𝑏𝑏𝑏, 𝑆𝐴𝐴𝑧) ⊢ (𝑞1, 𝑏𝑏𝑏𝑏, 𝐴𝐴𝑧) ⊢ (𝑞1, 𝑏𝑏𝑏, 𝐵𝐴𝑧)

⊢ (𝑞1, 𝑏𝑏, 𝐴𝑧) ⊢ (𝑞1, 𝑏, 𝐵𝑧) ⊢ (𝑞1, 𝜆, 𝑧) ⊢ (𝑞2, 𝜆, 𝑧)

---

• 주어진 CFG로부터 nPDA 생성
  • GNF가 아닌 경우는 어떻게 처리할까요?
  • 𝐺 = (𝑉, 𝑇, 𝑆, 𝑃)
  • ∀𝐴 → 𝛼
    • 𝛿 (𝑞, 𝜆, 𝐴) → {(𝑞, 𝛼) (𝐴 ∈ 𝑉)
    • 𝛿 (𝑞, 𝑎, 𝑎) → {(𝑞, 𝜆)} (𝑎 ∈ 𝑇)
    • 기본 아이디어
      • 남은 입력 = 스택

---

 

• 주어진 CFG로부터 nPDA 생성
  • 예시: 𝑆 → 𝐴𝑆 𝜆, 𝐴 → 𝑎𝐴𝑏 𝐴𝑏 | 𝑎𝑏
    • 𝛿 (𝑞0, 𝜆, 𝑧) → {(𝑞1, 𝑆𝑧)}
    • 𝛿 (𝑞1, 𝜆, 𝑆) → {(𝑞1, 𝐴𝑆) , (𝑞1, 𝜆)}
    • 𝛿 (𝑞1, 𝜆, 𝐴) → {(𝑞1, 𝑎𝐴𝑏) , (𝑞1, 𝐴𝑏) , (𝑞1, 𝑎𝑏)}
    • 𝛿 (𝑞1, 𝑎, 𝑎) → {(𝑞1, 𝜆)}
    • 𝛿 (𝑞1, 𝑏, 𝑏) → {(𝑞1, 𝜆)}
    • 𝛿 (𝑞1, 𝜆, 𝑧) → {(𝑞2, 𝜆)}

• Processing "𝑎𝑎𝑏𝑏𝑏"

(𝑞0, 𝑎𝑎𝑏𝑏𝑏, 𝑧)

⊢ (𝑞1, 𝑎𝑎𝑏𝑏𝑏, 𝑆𝑧) ⊢ (𝑞1, 𝑎𝑎𝑏𝑏𝑏, 𝐴𝑆𝑧)

⊢ (𝑞1, 𝑎𝑎𝑏𝑏𝑏, 𝑎𝐴𝑏𝑆𝑧) ⊢ (𝑞1, 𝑎𝑏𝑏𝑏, 𝐴𝑏𝑆𝑧) ⊢ (𝑞1, 𝑎𝑏𝑏𝑏, 𝐴𝑏𝑏𝑆𝑧)

⊢ (𝑞1, 𝑎𝑏𝑏𝑏, 𝑎𝑏𝑏𝑏𝑆𝑧) ⊢ (𝑞1, 𝑏𝑏𝑏, 𝑏𝑏𝑏𝑆𝑧) ⊢ (𝑞1, 𝑏𝑏, 𝑏𝑏𝑆𝑧)

⊢ (𝑞1, 𝑏, 𝑏𝑆𝑧) ⊢ (𝑞1, 𝜆, 𝑆𝑧) ⊢ (𝑞1, 𝜆, 𝑧) ⊢ (𝑞2, 𝜆, 𝑧)

 

---

• 주어진 CFG로부터 nPDA 생성: 연습
  • 예시: 𝑆 → 𝜆 | 𝑎𝑆𝑏 | 𝑏𝑆𝑎 | 𝑆𝑆

---

PDA to CFG

• 주어진 nPDA로부터 CFG 생성
  • 주의사항 - 이것은 매우 복잡합니다
  • 우리는 다음과 같은 유형의 nPDA를 고려합니다
    • 단 하나의 최종 상태만을 가지며 스택이 비어있을 때만 최종 상태로 진입할 수 있는 nPDA
    • 각각의 심볼 𝑎에 대한 전이가 스택 내용을 하나의 요소씩 증가시키거나 감소시킵니다
      • 예를 들어, 𝛿 (𝑞𝑖, 𝑎, 𝐴) = (𝑞𝑗, 𝜆) 또는 𝛿 (𝑞𝑖, 𝑎, 𝐴) = (𝑞𝑗, 𝐵𝐶)
  •  어떤 nPDA든 위의 조건을 만족하는 nPDA로 변환할 수 있습니다.

---

• 주어진 nPDA로부터 CFG 생성
  • 경우 (1)  𝛿 (𝑞𝑖, 𝑎, 𝐴) = (𝑞𝑗, 𝜆)
    • CFG는 규칙을 가지며, (𝑞𝑖𝐴𝑞𝑗) → 𝑎
    • (𝑞𝑖𝐴𝑞𝑗) 는 상태 𝑞𝑖에서 상태 𝑞𝑗 로 이동하는 동안 스택에서 𝐴를 팝하기 위한 것입니다.
  • 경우 (2)  𝛿 (𝑞𝑖, 𝑎, 𝐴) = (𝑞𝑗,𝐵𝐶)
    • CFG는 규칙을 가지며, (𝑞𝑖𝐴𝑞𝑘) → 𝑎(𝑞𝑗𝐵𝑎𝑙) (𝑞𝑙𝐶𝑞𝑘)
      • 𝑞𝑙 및 𝑞𝑘는 모두 Q에 속하는 가능한 상태들입니다.
      • (𝑞𝑖𝐴𝑞𝑘) → 𝑎 (𝑞𝑗𝐵𝑎𝑙) (𝑞𝑙𝐶𝑞𝑘)
        • 𝐴를 팝하고 상태 𝑞𝑖에서 상태 𝑞𝑘로 이동하는 한 가지 방법은 𝑎를 읽은 다음,
        • 상태 𝑞𝑗에서 상태 𝑞𝑙로 이동하면서 스택에서 𝐵를 팝하기 위해 일부 입력을 사용한 다음,
        • 스택에서 𝐶를 팝하고 상태 𝑞𝑙에서 상태 𝑞𝑘로 이동하는 입력을 더 읽는 것입니다.
  • 시작 변수 = (𝑞0𝑧𝑞f)

---

• 주어진 nPDA로부터 CFG 생성
  • Example (𝑞0: initial state, 𝑞2: final state)
    • 𝛿 (𝑞0, 𝑎, 𝑧) = {(𝑞0, 𝐴𝑧)}
    • 𝛿 (𝑞3, 𝜆, 𝑧) = {(𝑞0, 𝐴𝑧)}
    • 𝛿 (𝑞0, 𝑎, 𝐴) = {(𝑞3, 𝜆)}
    • 𝛿 (𝑞0, 𝑏, 𝐴 )= {(𝑞1, 𝜆)}
    • 𝛿 (𝑞1, 𝜆, 𝑧) = {(𝑞2, 𝜆)}

• 𝛿 (𝑞0, 𝑎, 𝑧) = {(𝑞0, 𝐴𝑧)}
• 𝛿 (𝑞3, 𝜆, 𝑧) = {(𝑞0, 𝐴𝑧)}
• 𝛿 (𝑞0, 𝑎, 𝐴) = {(𝑞3, 𝜆)} => 𝒒𝟎𝑨𝒒𝟑 → 𝑎
• 𝛿 (𝑞0, 𝑏, 𝐴 )= {(𝑞1, 𝜆)} => 𝒒𝟎𝑨𝒒𝟏 → 𝑏
• 𝛿 (𝑞1, 𝜆, 𝑧) = {(𝑞2, 𝜆)} => 𝒒𝟏𝒛𝒒𝟐 → 𝜆

---

• 𝛿 (𝑞3, 𝜆, 𝑧) = (𝑞0, 𝐴𝑧)
• (𝑞3𝑧𝑞0) → 𝑞0𝐴𝑞0 𝑞0𝑧𝑞0 | 𝑞0𝐴𝑞1 𝑞1𝑧𝑞0 | 𝑞0𝐴𝑞2 𝑞2𝑧𝑞0 | 𝑞0𝐴𝑞3 𝑞3𝑧𝑞0 ,
• (𝑞3𝑧𝑞1) → 𝑞0𝐴𝑞0 𝑞0𝑧𝑞1 | 𝑞0𝐴𝑞1 𝑞1𝑧𝑞1 | 𝑞0𝐴𝑞2 𝑞2𝑧𝑞1 | 𝑞0𝐴𝑞3 𝑞3𝑧𝑞1 ,
• (𝑞3𝑧𝑞2) → 𝑞0𝐴𝑞0 𝑞0𝑧𝑞2 | 𝑞0𝐴𝑞1 𝑞1𝑧𝑞2 | 𝑞0𝐴𝑞2 𝑞2𝑧𝑞2 | 𝑞0𝐴𝑞3 𝑞3𝑧𝑞2 ,
• (𝑞3𝑧𝑞3) → 𝑞0𝐴𝑞0 𝑞0𝑧𝑞3 | 𝑞0𝐴𝑞1 𝑞1𝑧𝑞3 | 𝑞0𝐴𝑞2 𝑞2𝑧𝑞3 | 𝑞0𝐴𝑞3 𝑞3𝑧𝑞3

---

---

Context-Free Languages

• 만약 어떤 NPDA 𝑴에 대해 𝑳 = 𝑳 𝑴 이라면, 𝑳은 문맥-자유 언어입니다.
• 어떤 언어가 문맥-자유 언어이면 그 언어는 어떤 NPDA에 의해 인정됩니다.
  • 모든 CFG에 대해 동등한 NPDA가 존재합니다.
  • 모든 NPDA에 대해 동등한 CFG가 존재합니다.