1. 다음 언어를 생성하는 문맥 민감 문법은 각각 무엇인가?

L_1 = { a^(n^2) | n ≥ 1 }

L_2 = { w^2 | w ∈ {a, b}^* }

L_3 = { (a^n)(b^m)(c^n)(d^m) | n, m ≥ 1 }

여기서 a, b, c, d는 심벌이다.


2. L_1, L_2 ⊆ {a, b}^*이고,

n_a(w)와 n_b(w)가 각각 문자열 w에 있는 a와 b의 개수일 때,

다음 언어를 생성하는 문맥 자유 문법을 고안하시오.

L_1 = { w | n_a(w) = n_b(w) }

L_2 = { w | n_a(w) = 2 * n_b(w) }


답은 밑에 있음. 물론 내가 생각한 답이어서 틀렸을 수도 ...































답:


1.1) P:

S → a

S → BA'

B → BC

B → C'

Caa → aaC

CA → aaAC

CA' → aaAA'

C'aa → aaC'

C'A → aaaC'

C'A' → aaaa


1.2) P:

S → aCS

S → bDS

S → aA

S → bB

Ca → aC

Cb → bC

Da → aD

Db → bD

CA → AA

CB → AB

DA → BA

DB → BB

A → a

B → b


1.3) P:

S → XY

X → aXC

X → aC

Y → BYd

Y → Bd

CB → BC

aB → ab

bB → bb

Cd → cd

Cc → cc


2.1) P:

S → aSbS | bSaS | λ


2.2) P:

S → aSaSbS | aSbSaS | bSaSaS | λ


여기서 λ는 빈 문자열이다.