[Automata] Context Free Grammar, Palindromes

Context Free Grammar, Palindromes

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

# Context Free Grammar

컴퓨터 프로그램을 만들기 위해서는 알고리즘이 필요하다.

사용자가 원하는 목적에 맞는 프로그램을 만들거나 특정한 프로그램을 개발하기 위해서는 알고리즘이 필요하다.

또한 알고리즘과 더불어 원하는 목적을 프로그램 방식에 맞게 구현해야 한다.

왜냐하면 사람이 당연하게 여기는 것들은 컴퓨터가 이해하지 못하기에 하나하나 특정한 방식으로 구현해줘야 하기 때문이다.

Regular expression과 같이 정규화된 방식으로 변경해주는 것도 프로그램화를 하는 방식 중에 하나이다.

문제는 어떤 경우에는 RE가 되지 않을 수 있다.

이렇때 정의하는 language 방식이 바로 Context free grammar이다.

줄여서 CFG라고 불리는 방식은 RE, 즉 Regular expression으로 구현이 안 되는 Language을 CFG로 정의할 수 있다.

---

# Formal Definition

CFG의 Foraml definition은 아래와 같다.

• N: A set whose elements called variables -> Non-terminals
• Σ: An alphabet. Elements of Σ called terminals.
• P: An element of N x (N U Σ)^*
• S: S ∈ N called start symobl

따라서 CFG는 (N, Σ, P, S)로 구성되어 있으며, 이렇게 나타내는 정의를 Formal definiton of CFG라고 부른다.

---

# Palindromes

CFG를 배우면 같이 따라오는 녀석이 바로 Palindromes이다.

왜냐하면 Palindromes는 CFG로 정의가 되기 때문이다.

Palindromes는 오른쪽과 왼쪽이 대칭을 이루고 있는 모양이며, 오른쪽에서 read하든 왼쪽에서 read하든 결과가 동일하다.

Set builder notation으로 Palindromes를 아래와 같이 나타낼 수 있다.

PAL = {w ∈ {0,1}^* | w^R = w}

위의 PAL 경우에는 0이나 1이 반복되는 w가 존재하며, w의 R 제곱은 w와 같다를 의미한다.

한마디로 w가 아무리 많아져도 w가 되며, 이를 Palindromes라고 부른다.

shorthand 방식으로도 정의가 가능한데, 예를 들어서 아래와 같이 표현이 가능하다.

P -> e, P-> 0, P -> 1, P-> 0P0, P -> 1P1

이러한 방식으로 표현된 정의들을 CFG라고 부른다.

---

# Derivation

위의 CFG로 정의된 shorthand 방식을 적용하여 문제를 풀 수 있는데, 이때 푸는 방법을 derivation이라고 부른다.

예를 들어서 01010이 존재한다고 가정했을 때,

P => 0P0 => 01 P10 => 01010으로 변환되어 문제를 풀 수가 있다.

이것을 우리는 Derivation이라고 하며, a1에서 시작하여 an까지 도달한다고 해서 Derivation sequence라고 한다.

Derivation을 사용하여 만든 시각적 구조체가 바로 Derivation trees 또는 Parse trees라고 한다.

---