[Compiler] 3-1. 형식 언어

• 언어: 알파벳으로 생성되는 모든 문자열들의 부분집합이다.
• 문법: 언어는 문법에 의해서 생성되고 정의된다.
• 인식기: 언어는 인식기에 의해 인식된다.

 

문법	언어	인식기
type 0(무제약 문법)	재귀 열거 언어	튜링 기계
type 1(문맥인식 문법)	문맥인식 언어	선형한계 오토마타
type 2(문맥자유 문법)	문맥자유 언어	푸시다운 오토마타
type 3(정규 문법)	정규 언어	유한 오토마타

알파벳

• 언어의 문장을 이루는 기본적인 기호(Symbol)로 정의한다.
• 공집합이 아닌 기호들의 유한 집합으로 \( \sum \)로 표시한다.
• 일반 프로그래밍 언어에서는 사용 가능한 문자나 기호들의 집합이라고 설명한다. C 언어의 경우 영문자, 숫자, 특수 문자 등이 해당된다.

문자열(String)

• 알파벳 \(\sum\) 에 대한 문자열은 알파벳에서 정의된 기호들을 나열한 유한 수열이다.
• 알파벳 \(\sum = {a, b, c}\) 일 때, a, ca, ccba 등이 문자열이 된다.

💡 문자열은 언어 이론에서 종종 문장(sentence)이나 단어(word)와 동의어로 사용된다. 언어를 구성하는 각각의 알파벳 기호들은 하나의 문자로 표시하는데 영어의 a, b, c 등을 주로 사용하고 문자열의 이름은 u, v, w 등으로 나타낸다. 예를 들어 w = abaaa는 abaaa라는 값을 갖는 문자열의 이름이 w임을 나타낸다.

문자열의 길이(Length)

• 문자열을 이루는 기호의 개수이다.
• 어떤 문자열 w의 길이는 |w| 로 표시하고, w의 카디널리티라고 읽는다.
• \(w_1=abc, w_2=abab\)의 문자열에 대한 길이를 구하라
  • \(|w_1|=3, |w_2|=4\)
• \(w=v_1v_2v_3\cdots v_k\)일 때 \(|w|=k\) 이다.
• 문제 예시
  • \(\sum\) 에 Length를 주고 가능한 문자열을 만들어라

문자열의 접속(Concatenation)

• 두 개의 문자열을 연결하여 새로운 문자열을 만드는 연산이다.
• 문자열 \(u, v\)가 각각 \(u=a_1a_2a_3\cdots a_n, v=b_1b_2b_3\cdots b_m\)일 경우에 두 문자열의 접속은 \(u\cdot v\) 혹은 \(uv\)로 표시하고 \(uv=a_1a_2a_3\cdots a_nb_1b_2b_3\cdots b_m\)이다.
• 두 문자열 \(u=dog, v=house\)가 있을 때 \(u\cdot v\)와 \(v\cdot u\)를 구하라
  • \(u\cdot v =doghouse, v\cdot u=housedog\)
• 위 예제에서 \(|u\cdot v|\)와 \(|v\cdot u|\)를 구하라
  • \(|u\cdot v|=|u| +|v|=|dog|+|house|=8\)
  • \(|v\cdot u|=|v| +|u|=|house|+|dog|=8\)

공문자열(Empty string)

• 문자열의 길이가 0인 문자열이다.
• \(\epsilon\) 으로 표기한다.
• 어떤 문자열 \(u, v\)에 대해 다음과 같은 속성을 가진다.
  • \(u\epsilon=u=\epsilon u\)
  • \(u\epsilon v=uv\)
• Empty string을 \(\lambda\)로도 표시하며 널 문자열이라고도 한다. 문자열에서 연산 중 접속 연산은 \(\epsilon\)을 항등원으로 취한다.
• \(a^n\)은 a가 n개 연결된 문자열을 표시하며, \(a^0\)은 공문자열을 나타낸다. 즉, \(a^n=aaa\cdots a\) 이고 \(a^0=\epsilon\)이 된다.

문자열의 역(reverse)

• \(w^R\)은 문자열 \(w\)의 역(reverse)로 \(w\)를 이루는 요소들의 역순으로 얻어진다.
  • 문자열 \(w=ccba\)에 대한 \(w^R\)
    • \(w^R=abcc\)

접두사(Prefix)

• 문자열 \(w=uv\)일 때 \(u\)를 문자열 \(w\)의 접두사라고 한다.
• 진접두사(Proper prefix): \(u\neq \epsilon\) 인 접두사
• 접미사(Suffix): 문자열 \(w=uv\)일 때 \(v\)를 문자열 \(w\)의 접두사라고 한다.
• 진접미사(Proper suffix): \(v\neq \epsilon\)인 접미사
• 문자열 \(w=house\) 일 때 다음을 구하시오
  • 접두사 - \(\epsilon, h, ho, hou, hous, house\)
  • 진접두사 - \(h, ho, hou, hous, house\)
  • 접미사 - \(house, ouse, use, se, e, \epsilon\)
  • 진접미사 - \(house, ouse, use, se, e\)

\(\sum^*\)(reflexive transitive closure, Kleene closure)

• 공문자열을 포함하는 알파벳 \(\sum\) 에 대한 접속 연산에 의해 만들어 질 수 있는 모든 문자열들의 집합이다.
• \(\sum\) - star, 클리니 클로저라고 읽는다.

\(\sum^+\)(transitive closure, positive closure)

• \(\sum^*\)에서 공문자열을 제외한 모든 문자열의 집합이다.
• \(\sum\) - dagger, 포지티브 클로저라고 읽는다.
• \(\sum^+=\sum^*-{\epsilon}\)

언어 \(L\)

• 알파벳 \(\sum\) 에 대해서 \(\sum^*\)의 부분집합

유한 언어

• 언어에 속하는 문자열의 수가 유한 개인 언어를 말한다.

무한 언어

• 언어에 속하는 문자열의 수가 무한 개인 언어를 말한다.

💡 언어는 의미(semantic)의 개념은 포함하지 않는다.

💡 언어란 단지 문자열들의 집합이기 때문에 형식 언어 이론은 문자열 집합의 속성에 관한 이론이다.

언어에서의 연산

두 언어의 합집합

• 두 언어 \(L\)과 \(M\)의 합집합 \(L\cup M\)은 \(L\)에 속하는 문자열이거나 \(M\)에 속하는 문자열이다.

두 언어의 접속

• 두 언어 \(L\)과 \(M\)의 접속은 \(LM\)은 \(L\)에 속하는 문자열과 \(M\)에 속하는 문자열을 접속한 것으로 교환 법칙은 성립하지 않는다.

\(L\)의 거듭제곱

• 언어 \(L\)의 거듭제곱은 재귀적으로 다음과 같이 정의한다.
• \(L^0=\epsilon\)
• \(L^n=LL^{n-1}\), 단 \(n\ge1\)

클리니 클로저, 포지티브 클로저

• 언어 \(L\)의 클리니 클로저 \(L^*\)는 다음과 같이 정의한다.
  • \(L^*=L^0\cup L^1\cup L^2\cup\cdots \cup L^n\cup \cdots=\bigcup_{i=0}^\infty L^i\)
• 언어 \(L\)의 포지티브 클로저 \(L^+\)는 다음과 같이 정의한다.
  • \(L^1\cup L^2\cup\cdots \cup L^n\cup \cdots=\bigcup_{i=1}^\infty L^i =L^*-L^0\)