언어, 문법

형식언어 (Formal Language)

형식언어에서는 정확성이 필수적이므로, 정확성을 위해 언어는 스트링의 집합으로 표현됩니다.

영어, 한국어 등의 자연어와의 차이점이 정확성 요구의 유무라고 볼 수 있습니다.

 

스트링에 앞서 기호(Symbols)를 먼저 설명하자면, 한 개 이상, 유한개의 기호로 구성된 집합으로 Decimal의 경우 0 ~ 9 라는 기호로 구성된 집합이고, Binary의 경우 0, 1 이라는 기호로 구성된 집합이라고 보시면 됩니다. 

 

스트링은 유한개의 기호들을 나열한 것입니다. 모든 기호는 그 자체로 스트링이 될 수 있고, 아무런 기호도 없는 스트링을 빈 스트링이라고 하는데, 그 존재를 설명하기 위해 특수 기호 λ(Lambda) 로 사용합니다. 하지만, 람다기호는 기호가 되지는 않습니다.

 

다음은 스트링의 연산입니다.

 

먼저 병합(Concatenation)은 병합 연산자 · 를 사용하여 두 스트링을 합쳐 새로운 스트링을 만드는 이진 연산자이며, 중간 표현식을 사용합니다. (Infix notation) 보통은 병합 연산자를 생략하고 wv와 같은 형식으로 사용합니다.

 

병합은 교환법칙은 성립하지 않으나, 결합법칙은 성립합니다.

Lambda와의 병합은 본래 스트링을 유지합니다. ex) wλ = w

 

결합법칙이 성립할 경우, 괄호를 생략해도 됩니다. 이때, 모호성을 갖게 되지만, 순서를 어떻게 바꾸어도 결과값이 같으므로 모호성이 있더라도 문제가 되지 않습니다.

 

스트링의 역(Reverse)는 인수를 한 개 가지는 연산자로서 연산자의 지수에 R로 표현합니다. w^R

ex) w = abc, w^R = cba

 

길이는 스트링 기호의 개수를 보여주는 연산자로 다음과 같이 사용합니다.

ex) w= abc, |w| = 3, |λ| = 0

이때, 병합된 스트링의 길이는 각 스트링 길이의 합으로 정의됩니다.

 

 서브스트링은 w = xyz일때, x,y,z는 각각 w의 서브스트링이과, x와 z는 각각 전위부(prefix), 후위부(suffix) 입니다.

λ는 모든 스트링의 전위부, 후위부, 서브스트링이됩니다.

 

지수(Exponentiation)는 한 스트링 w에 대해 병합이 n번 적용되는 것으로, w^n으로 표기합니다.

ex) w = abc, w^0 = λ, w^2 = abcabc

 

언어(Language)는 주어진 기호들에 대해 스트링들이 정의되고, 해당 스트링들의 집합으로 언어 L이 정의됩니다.

언어는 집합으로 정의되어 있으므로, 기존 집합 연산자(합집합, 곱집합, 차집합, 여집합, 지수 등..)들이 이용될 수 있습니다.

 

L* 는 언어에 star-closure를 붙인 기호로, L의 지수 0부터 쭉 상승하는 언어들의 합집합입니다. (L^0 ∪ L^1 ∪ L^2 ∪ ...)

즉, 무한집합이고, λ를 포함합니다.

 

L+ 는 언어에 positive-closure를 붙인 기호로, L*에서 λ를 포함하지 않는 차이가 있습니다.

 

문법 (Grammars)

문법 G는 다음 4가지 요소로 구성됩니다.

 

G = (V, T, S, P)

 

V는 넌터미널, T는 터미널, S는 넌터미널 중 시작 넌터미널 1개를 의미하고, P는 유한개의 생성 룰을 의미합니다.

생성 룰의 경우, →를 기준으로 왼쪽과 오른쪽의 두 부분으로 구성됩니다. (x → y) 이때, x는 한개의 넌터미널이고, y는 터미널과 넌터미널로 구성됩니다.

ex) G = ({S}, {a, b}, S, P) P = (S → aSb, S → λ)

 

문법에 의한 스트링 생성은 기호 ⇒로 표기합니다.

 

위의 예시로 나온 문법 G의 경우, S ⇒ aSb ⇒ aaSbb ⇒ aabb. 로, 스트링 aabb를 생성합니다.

이를 축약하여 S ⇒* aabb. 로 표기합니다.

 

문법 G는 aabb말고도, λ, ab, aabb 등 여러 스트링의 무한집합을 만들어냅니다. 이는 곧, 문법 G에 해당하는 언어를 표현합니다.