카테고리 없음

[계산이론] Simplification of Context-Free Grammars and Normal Forms - 1

7_JUN_7 2023. 10. 24. 05:53

Context-Free Grammars (문맥 자유 문법)

 

CFG는 불필요한 규칙을 포함할 수 있다.

  • 예를 들어, 다음의 생산 규칙을 가진 문맥자유문법 G를 고려하자.
    • 𝑆 → 𝑎𝑆𝑏 | 𝜆 | 𝐴
    • 𝐴 → 𝑎𝐴
  •  여기서, 𝑆 → 𝐴 는 아무 역할도 하지 않는다.
    • 𝐴는 터미널 문자열로 변환될 수 없다 (문장을 생성할 수 없다).
  •   따라서, 𝑆 → 𝐴와 𝐴 → 𝑎𝐴를 제거할 수 있다.
    • 언어에는 영향이 없다!

세 가지 간소화(simplification) 기법

  1. 𝜆-생산물 제거 ( Eliminating 𝜆 −productions)
  2. 단위 생산물 제거 ( Eliminating unit productions)
  3. 불필요한 변수 제거 ( Eliminating useless variables)

 

Simplification of Context-Free Grammars (문맥자유문법 간소화)

 

𝜆-생산물 제거

  • CFG의 형태로 주어진 𝐴 → 𝜆 같은 어떤 생산물을 𝜆-생산물이라고 부릅니다.
  • 𝐴 ֜∗𝜆의 파생이 가능한 어떤 변수 𝐴를 nullable(비어 있는)이라고 합니다.

 

문법은 𝝀를 포함하지 않는 언어를 생성할 수 있지만, 일부 𝝀-생산물 또는 nullable 변수를 가질 수 있습니다.

  • 이 경우, 𝜆-생산물은 제거할 수 있습니다.

 

𝜆-생산물 제거 : 예시 문제

  • 다음 문법을 고려해보세요.
    • 𝑆 → 𝑎𝑆1𝑏
    • 𝑆1 → 𝑎𝑆1𝑏 | 𝜆
      • 이것은 𝐿 𝐺 = 𝑎𝑛𝑏𝑛 : 𝑛 ≥ 1 (여기서 𝜆 ∉ 𝐿 𝐺 )의 언어를 생성합니다.
      • 따라서, 우리는 𝜆-생산물을 제거할 수 있습니다.
        • 𝑆 → 𝑎𝑆1𝑏 | 𝑎𝑏
        • 𝑆1 → 𝑎𝑆1𝑏 | 𝑎𝑏

𝜆-생산물을 어떻게 제거할 수 있을까요?

  1. 모든 nullable 변수를 찾습니다.
  2. 𝜆-생산물을 제외하고 모든 조합에서 nullable 변수를 𝜆로 대체하여 생성된 생산 규칙을 사용하여 새 CFG를 구성합니다.

 

𝜆-생산물 제거 : 예시 문제

  • 문법을 고려해보세요
    • 𝑆 → 𝐴𝐵𝑎𝐶
    • 𝐴 → 𝐵𝐶
    • 𝐵 → 𝑏 | 𝜆
    • 𝐶 → 𝐷 | 𝜆
    • 𝐷 → 𝑑

 

  •  Nullable 변수: (𝐴, 𝐵, 𝐶)
  • Nullable 변수를 𝜆로 교체합니다 (예: 𝑆의 𝐴, 𝐵, 𝐶를 𝜆로 교체)

 

  • 𝜆-생산물이 없는 결과 문법
    • 𝑆 → 𝐴𝐵𝑎𝐶, 𝐵𝑎𝐶, 𝐴𝑎𝐶, 𝐴𝐵𝑎, 𝑎𝐶, 𝐴𝑎, 𝐵𝑎, 𝑎
    • 𝐴 → 𝐵𝐶, 𝐵, 𝐶
    • 𝐵 → 𝑏
    • 𝐶 → 𝐷
    • 𝐷 → 𝑑

 

단위 생산물 제거

 

  • CFG의 형태인 𝐴 → 𝐵의 모든 생산물을 단위 생산물이라고 합니다.
    • 𝐴, 𝐵 ∈ 𝑉 × 𝑉의 변수 쌍은 𝐴 ֜∗𝐵인 경우 단위 쌍입니다.
    • 모든 𝐴 ∈ 𝑉에 대해 𝐴, 𝐴는 단위 쌍입니다.

 

단위 생산물을 어떻게 제거합니까?

  1. 모든 단위 쌍을 찾습니다.
  2. 각 단위 쌍 𝐴, 𝐵에 대해 가능한 모든 비단위 생산물을 추가하여 새로운 CFG를 구성합니다.

 

 

단위 생산물 제거: 예시 문제

 

  • 문법을 고려하십시오.
    • 𝑆 → 𝐴𝑎 | 𝐵
    • 𝐴 → 𝑎 𝑏𝑐 𝐵
    • 𝐵 → 𝐴 | 𝑏𝑏

 

  • 모든 단위 쌍: (𝑆, 𝑆), (𝐴, 𝐴), (𝐵, 𝐵), (𝑆, 𝐴), (𝑆, 𝐵), (𝐴, 𝐵), (𝐵, 𝐴)

 

  • (𝑆, 𝑆), (𝐴, 𝐴), (𝐵, 𝐵)에서 비단위 생산물을 고려하십시오.
    • 𝑆 → 𝐴𝑎
    • 𝐴 → 𝑎 | 𝑏𝑐
    • 𝐵 → 𝑏𝑏
  • (𝑆, 𝐴), (𝑆,𝐵), (𝐴, 𝐵), (𝐵, 𝐴)에서 가능한 비단위 생산물을 고려하십시오.
    • 𝑆 → 𝑎 | 𝑏𝑐 | 𝑏𝑏
    • 𝐴 → 𝑏𝑏
    • 𝐵 → 𝑎 | 𝑏𝑐

  • 비단위 생성물이 없는 결과 문법
    • 𝑆 → 𝐴𝑎 | 𝑎 | 𝑏𝑐 | 𝑏𝑏
    • 𝐴 → 𝑎 | 𝑏𝑐 | 𝑏𝑏
    • 𝐵 → 𝑎 | 𝑏𝑐 | 𝑏𝑏

단위 생산물 제거: 예시 문제2

  • 단위 생성 없이 동등한 CFG 설계하라
    • 𝐸 → 𝐸 + 𝑇 | 𝑇
    • 𝑇 → 𝑇 ∗ 𝐹 | 𝐹
    • 𝐹 → 𝐸 | 𝑎

 

  • 단위 생성이 없는 결과 문법
    • 𝐸 → 𝐸 + 𝑇 | 𝑇 ∗ 𝐹 | 𝐸 | 𝑎
    • 𝑇 → 𝑇 ∗ 𝐹 | 𝐸 | 𝑎
    • 𝐹 → 𝐸 | 𝑎

 

무용한 변수 제거 ( Eliminating useless variables)

  • 변수 𝐴 ∈ 𝑉는 최소한 하나의 𝑤 ∈ 𝐿(𝐺)가 있어서 𝑆 ֜∗ 𝑥𝐴𝑦 ֜∗ 𝑤 (여기서 𝑥, 𝑦 ∈ 𝑉 ∪ 𝑇∗) 를 만족할 때 유용하다고 말한다.
  • 다시 말해, 변수는 최소한 하나의 파생에서 나타나는 경우에만 유용하다.
  • 유용하지 않은(not useful) 변수는 무용하다( useless)고 불린다.

 

 

 

무용한 변수 제거: 예시 문제

 

  • 다음의 생성 규칙을 가진 CFG를 고려하십시오.
    • 𝑆 → 𝐴𝑎 𝑎 𝑏𝑐 | 𝑏𝑏
    • 𝐴 → 𝑎 𝑏𝑐 𝑏𝑏 
    • 𝐵 → 𝑎 𝑏𝑐 𝑏𝑏
  • 변수 B는 무용하다!

 

무용한 변수를 어떻게 제거하나요?

  1. 모든 무용한 변수를 찾습니다.
  2. 그 변수들을 제거합니다!

 

 

예시 문제

 

  • 생산 규칙을 가진 CFG를 고려해보세요.
    • 𝑆 → 𝑎𝑆 𝐴 𝐶
    • 𝐴 → 𝑎
    • 𝐵 → 𝑎𝑎
    • 𝐶 → 𝑎𝐶𝑏
  •  시작 변수에서 도달할 수 없는 𝐵가 있습니다.
  • 𝐶는 어떠한 단어도 유도할 수 없습니다.

  • 무용한 변수가 없는 결과 문법
    • 𝑆 → 𝑎𝑆 | 𝐴
    • 𝐴 → 𝑎

실습 문제 1

  • 단위 생산이 없는 동등한 CFG 설계하라
    • 𝑆 → 0𝐴 1𝐵 𝐶
    • 𝐴 → 0𝑆 | 00
    • 𝐵 → 1 | 𝐴
    • 𝐶 → 01

 

실습 문제 2

 

  • 𝜆-생산 없이 동등한 CFG를 설계하십시오.
    • 𝑆 → 𝐴𝐵𝐶
    • 𝐴 → 𝑎 | 𝑏𝑏𝐷
    • 𝐵 → 𝑎 | 𝜆
    • 𝐶 → 𝑏 | 𝜆
    • 𝐷 → 𝑐 | 𝑎