형식 언어

형식 언어는 일상생활에서 익숙한 ‘언어’라는 개념을 일반화한 것이다.

기본 개념

처음에는 형식 언어를 한국어나 영어 같은 일상 언어처럼 생각해도 된다. 이런 언어는 무엇으로 이루어져 있을까? 단어로 이루어져 있고, 단어를 이어 문장을 만든다. 여기서 문장은 다루지 않고 단어만 다룬다. 그러면 단어는 무엇으로 이루어져 있을까? 알파벳의 글자로 이루어져 있다. 그래서 알파벳부터 시작한다.

알파벳은 공집합이 아닌 임의의 집합이다. 알파벳의 원소를 기호라고 한다. 영어라면 소문자와 대문자를 모두 포함한 보통의 로마자 알파벳이 되고, 한국어라면 한글 글자 전체가 된다. 언어가 아니라 수를 나타내고 싶다면 알파벳에는 숫자 10개가 들어간다. 알파벳은 흔히 기호 Σ로 나타낸다.

문자열(단어라고도 한다)은 어떤 알파벳 Σ의 기호를 늘어놓은 유한한 수열이다. 예를 들어 알파벳이 Σ= {a,b,c,d,e,…, z}이면 “hello”나 “doberman”은 문자열이지만 “café”(글자 “é”가 없다), “Seoul”(글자 “S”가 없다), “good day”(공백이 없다)는 문자열이 아니다. 문자열을 이루는 기호의 개수를 문자열의 길이라고 한다.

문자열의 연접: 두 문자열 a = a₁a₂… a_n과 b = b₁b₂… b_m이 있을 때, 두 문자열을 연접하면 문자열 ab = a₁a₂… a_nb₁b₂… b_m이 만들어진다. 예를 들어 “hello”와 “doberman”을 연접하면 “hellodoberman”이 된다. 연접은 동그라미를 써서 a ∘ b로 나타내거나, 아무 기호 없이 두 문자열을 이어 쓰기만 한다.

빈 문자열은 길이가 0인 문자열이고 ε으로 나타낸다. 문자열 a = a₁… a_n에 빈 문자열 ε을 연접하면 다시 문자열 a가 된다. 즉 a ∘ ε = a가 성립한다.

알파벳 Σ의 클레이니 폐포는 빈 문자열을 포함하여 알파벳 Σ로 만들 수 있는 모든 문자열의 집합이다. 클레이니 폐포는 Σ^∗로 나타낸다. 이진 알파벳 Σ= {0, 1}이면 다음이 성립한다.

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

알파벳의 양의 폐포를 쓰기도 한다. 이것도 알파벳으로 만들 수 있는 모든 문자열의 집합인데, 빈 문자열만 뺀다. 양의 폐포는 Σ⁺로 나타내고 Σ⁺ = Σ^∗ ∖ {ε}이 성립한다.

알파벳의 예

• 한국어의 예로 돌아가 보자. 한국어 단어는 모두 한글 글자로 이루어진 알파벳의 클레이니 폐포에 들어 있다(하이픈 “-”도 넣어야 할 수 있다). 이 알파벳에 공백과 문장 부호(쉼표, 마침표, 느낌표, 물음표, …)를 더하면, 그 클레이니 폐포에는 한국어로 쓸 수 있는 모든 문장이 들어간다. 물론 이 폐포에는 “ㅁ넝ㄹ 뷁쀍 갉쀍깱 ㄴㅇ!!!:??: ::!?:?:ㅋㅋ” 같은, 아무 의미 없는 문장도 들어 있다.

• 알파벳이 숫자 전체 Σ= {0, 1, …, 9}이면 클레이니 폐포에는 모든 자연수가 들어 있고, 그 밖의 것도 들어 있다. 00054처럼 0으로 시작하는 수와 0 자체도 들어 있고, 수가 아닌 빈 문자열도 들어 있다.

• 알파벳은 공집합이 아니어야 하므로 가장 작은 알파벳에도 기호가 적어도 1개 있다. 예를 들어 알파벳 Σ= {!}의 클레이니 폐포는 Σ^∗ = {ε, !, !!, !!!, !!!!, …}이다. 즉 각 n ∈ ℕ₀(0 이상의 정수)에 대하여 느낌표가 n개인 문자열이 폐포에 있고, 다른 문자열은 없다.

• Σ= {qw,c}라고 하자. 이 알파벳은 문자열 qw를 포함하므로 아주 특이하다. 헷갈리고 이상해서 보통은 이렇게 쓰지 않지만, 글자 “q”와 “w”를 붙여 한 글자로 만들었다고 생각하면 된다. 그러면 문자열 “qw”를 기호 “qw” 하나로 볼 수 있다. 이 기호로 문자열 “qwcqw”를 만들면 이 문자열의 길이는 3이다. 기호 “qw”, “c”, “qw”로 이루어지기 때문이다. 이런 알파벳은 자주 나오지 않지만, 여러 글자로 이루어진 기호가 필요한 경우도 있다.

형식 언어

알파벳 Σ 위의 (형식) 언어는 Σ^∗의 임의의 부분집합이다. 따라서 알파벳 Σ 위의 언어 L에 대하여 L ⊆ Σ^∗가 성립한다. 언어의 예는 다음과 같다.

• 앞에서 숫자의 알파벳 Σ= {0, 1, …, 9}를 정의했다. 그 클레이니 폐포는 숫자로만 이루어진 모든 문자열의 집합이다. 여기에 문자열이 0으로 시작하면 안 되고 빈 문자열이어도 안 된다는 규칙을 더하면 자연수의 집합 ℕ을 얻는다. ℕ ⊆ Σ^∗가 성립하므로 ℕ은 알파벳 Σ 위의 언어이다.

• 앞의 숫자 집합에 빼기 기호 “-”를 더하여 Σ= {0, 1, …, 9, −}로 둘 수도 있다. 그 클레이니 폐포는 숫자나 빼기 기호로 이루어진 모든 문자열의 집합이다. 그런데 그러면 “12-84-”, “1-5-8”, “-” 같은 문자열도 폐포에 들어 있다. 정수의 언어 ℤ는 다음 세 규칙을 더하여 만든다.

  • 빼기 기호는 문자열에 아예 없거나 문자열의 맨 앞에만 있다.
  • 문자열 “0”을 제외하면 문자열의 첫 숫자는 0이 될 수 없다.
  • 모든 문자열에는 숫자가 적어도 1개 있어야 한다.

  이 집합은 정수의 집합을 나타내고 집합 Σ^∗의 부분집합이다. 따라서 알파벳 Σ 위의 언어이다.

• Σ= {0, 1}이라고 하자. 그러면 클레이니 폐포는 0과 1로 이루어진 모든 문자열의 집합이다. 이 알파벳 위의 언어 L은 예를 들어 1이 3개인 모든 문자열의 집합으로 정의할 수 있다. 더 창의적으로, 언어 L을 올바른 docx 파일 형식(Word에서 저장한 파일)을 나타내는 모든 문자열의 집합으로 정할 수도 있다.

• 이진 알파벳 Σ= {0, 1}을 계속 쓰자. 키보드에 있는 보통의 문자로 이루어진 문자열은 모두 이진 형태, 즉 0과 1로 바꿀 수 있고 다시 되돌릴 수도 있다. 예를 들어 ASCII 코드표를 쓰면 된다(정확히 말하면 ASCII 코드표는 문자를 수로 바꾸고, 십진법의 수는 이진법의 수로 바꿀 수 있다). 따라서 올바른 이메일 주소에 해당하는 모든 문자열의 언어를 정의할 수 있고, 이것도 이진 알파벳 위의 언어이다.

언어의 연접: 언어도 연접할 수 있다. 정의는 집합의 곱집합과 비슷하다. 두 언어 L₁과 L₂가 있다고 하자. 이를 연접한 L₁ ∘ L₂는 다음과 같이 정의하는 새 언어이다.

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

즉 언어 L₁의 모든 문자열에 언어 L₂의 모든 문자열을 연접한다. 예를 들어 다음과 같다고 하자.

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,hello\}\end{array}$$

그러면 다음이 성립한다.

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0hello,1a,1b,1hello\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,hello0,hello1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

지금까지는 언어를 일상 언어로, 즉 언어가 어떤 모습인지 말로 설명했다. 하지만 이 방법은 매우 불편하므로 언어를 정의하는 더 형식적인 방법을 쓴다. 그 첫 번째가 문법이다.