프로그래밍 언어 5장 형식언어

5. 형식 언어

형식 언어는 정규 언어가 될 수 있지만 정규 언어는 형식 언어가 반드시 될 수는 없음

정규 언어는 유한 오토마타로 식별 가능

형식 언어는 유한 오토마타와 튜링 머신으로 식별 가능

형식언어

우리가 컴퓨터에게 명령하고 싶다면, 훨씬 더 정확한 것을 사용해야 한다.

구문과 의미가 정확한 언어를 형식 언어(formal languages)라고 한다.

심볼 (Symbol)

언어를 이루는 가장 기본적인 단위 혹은 기호다.

한국어는 ‘ㄱ’, ‘ㄴ’, … , ‘ㅡ’, ‘ㅣ’가 있지만 영어는 ‘a’, ‘b’, ‘c’, … , ‘z’가 있다.

알파벳 (Alphabet)

• 문자, 숫자, 특수 기호 등으로 구성 유한한 기호들의 집합이다.
• 비어있으면 안된다.
• 기호로는 $\Sigma$로 표현이 가능하다.

• 영어 알파벳은 아래와 같이 표기가 가능하다.

  \[\sum = \{ a, b, c, d, e, … , y, z \}\]

문자열 (String)

• 알파벳에서 선택하여 나열한, 유한한 심볼들이다.

예를 들기위해 위에 알파벳에서 설명한 영어 알파벳 $\Sigma$에서 심볼을 선택해서 나열해보자.

\[\{ apple, banana, aaaaaa, zzzzzz \}\]

위 집합은 영어의 문자열이다.

하지만, 집합에 영어가 아닌 숫자나 한글이 끼게 되면 영어의 문자열이 될 수 없다.

• 공집합 또한 문자열이 될 수 있다.
• 이를 엡실론 (epsilon) 기호로는 $\epsilon$로 표현한다.

언어 (Language)

• 언어는 알파벳 시그마 스타의 부분집합이다.

시그마 스타란?

이 개념을 이해하기 위해서는 시그마 제곱수를 이해해야 한다.

시그마 제곱수는 \(\sum^k\)로 나타낼 수 있다.

영어 알파벳 \(\sum^1\)은 아래와 같다.

\[\sum^1 = \{ a, b, c, d, e, … , z\}\]

그냥 \(\sum\)와 같다고 볼 수 있다.

영어 알파벳 \(\sum^2\)는 아래와 같다.

\[\sum^2 = \{ aa, ab, ac, ad, ae, … , zy, zz\}\]

추가적으로 알아둬야 할 것은 \(\sum^0=\{\epsilon\}\) 란 것이다.

이제 시그마 스타에 대해 알아보자

기호로 \(\sum^*\)라고 나타내며 아래와 같이 정의한다.

\[\sum^{0}=\{\varepsilon \}\] \[\sum^{1} = \sum\] \[\sum^{n} = \sum \circ \sum^{n-1}\]

일때,

\[\sum^{*} = \bigcup_{i=0}^\infty \sum^{i} = \sum^{0} \bigcup \sum^{1} \bigcup \sum^{2} \bigcup …\]

어떤 알파벳 \(\sum\)로 만들 수 있는 모든 문자열의 집합이라고 생각하면 된다.

예로 보면 쉽게 알 수 있다.

\(\sum = \{ 0, 1 \}\)란 알파벳이 있다고 가정하면 아래와 같다.

\[\sum^{0}=\{\varepsilon \}\] \[\sum^{1} = \{0,1\}\] \[\sum^{2} = \{ 00, 01, 10, 11 \}\] \[\sum^{3} = \{ 000, 001, 010, 011, 100, 101, 110, 111 \}\] \[.....\] \[\sum^{*} = \{ \varepsilon, 0, 1, 00, 01, … , 1110, 1111, … \}\]

가 된다.

• 알파벳 시그마 스타는 그 알파벳으로 만들 수 있는 모든 문자열의 집합이고, 그 부분집합이 바로 언어라는 것이다.

쉽게 설명하면 아래와 같다.

1. 어떤 알파벳 \(\sum_{한글}\)은 “꿻뿱”이라는 문자열부터 “가위”라는 문자열까지 무한하게 많은 문자열을 만들 수 있다. (\(\sum_{한글}^*\))
2. 이때, 어떤 언어 \(L_{한국어}\)는 “가위”라는 문자열을 포함한 알파벳 \(\sum_{한글}\)의 유한한 문자열만을 포함한다.즉, 한글로 이루어져 있는 유한한 문자열만을 포함한다.
3. \(∑^∗_{한글}\)의 부분집합이 성립하기 때문에 언어 \(L_{한국어}\)는 언어다.

알파벳 시그마 스타의 부분집합이기만 하면 언어가 될 수 있기 때문에, 다음과 같은 언어도 존재한다.

\(L_1 = \emptyset\)(비어있는 언어)

\(L_2 = \{ \varepsilon \}\)(앱실론만 포함하는 언어)

둘은 엄연히 다른 언어다. (\(L_1 \neq L_2\))

형식언어의 연산

문자열의 연산

문자열 \(w_1 = abcd, w_2 = 01\)이라 하고 연산을 해보자.

문자열의 길이

\[| w_1 | = 4\] \[| w_2 | = 2\]

문자열 결합

\[w_1 \cdot w_2 = w_1w_2 = abcd01\] \[w_2 \cdot w_1 = w_2w_1 = 01abcd\]

빈 문자열 \(\varepsilon\)은 어느 문자열에도 결합이 가능하다.

\[w_2 = 01 = \varepsilon0\varepsilon1\varepsilon = …\varepsilon\varepsilon0\varepsilon\varepsilon…\varepsilon\varepsilon1\varepsilon\varepsilon…\]

평소에는 생략되어있다고 생각하면 된다.

접두사

만약 \(z = w_1w_2\)라면, \(w_1\)은 \(z\)의 접두사다.

\(\varepsilon, a, ab, abc, abcd\)는 \(w_1\)의 접두사다.

\(\varepsilon, 0, 01\)는 \(w_2\)의 접두사다.

접미사

만약 \(z = w_1w_2\)라면, \(w_2\)는 \(z\)의 접미사다.

\(\varepsilon, a, ab, abc, abcd\)는 \(w_2\)의 접미사다.

\(\varepsilon, 0, 01\)는 \(w_2\)의 접미사다.

부분 문자열

만약 \(z = w_1w_2\)라면, \(w_1\)과 \(w_2\)는 \(z\)의 부분 문자열이다.

\(\varepsilon, a, b, c, d, ab, ac, ad, …, abcd\)는 \(w_1\)의 부분 문자열이다.

\(\varepsilon, 0, 1, 01\)는 \(w_2\)의 부분 문자열이다.

반전

\(w_1\)의 반전은 \(dcba\)다.

\(w_2\)의 반전은 \(10\)이다.

회문

문자열의 반전이 원래 문자열과 동일한 문자열을 말함.

\(aba\)의 반전은 \(aba\)이므로 회문임.

\(01\)의 반전은 \(10\)이므로 회문이 아님.

언어의 연산

언어 \(L_1 = \{ a, b, c\}, L_2 = \{ a, z \}\)가 있다 가정하고, 연산을 해보자.

합집합 union

두 언어 \(L_1, L_2\)가 갖는 모든 문자열을 포함하는 연산이다.

\[L_1 \cup L_2 = \{ a, b, c, z \}\]

교집합

두 언어 \(L_1, L_2\)가 모두 갖는 문자열만 포함한 연산이다.

\[L_1 \cap L_2 = \{ a \}\]

여집합

한 언어 \(L_1\)이 앒파벳으로 만들 수 있는 모든 문자열에서, \(L_1\)이 갖는 문자열을 제외한 모든 문자열을 포함한 연산이다.

\[L_1 = \sum^* - L_1\]

접합

두 언어 \(L_1, L_2\)가 갖는 모든 문자열을 결합 하는 연산이다.

\[L_1 \cdot L_2 = \{ aa, az, ba, bz, ca, cz \}\]

반전

한 언어 \(L_1\)이 갖는 모든 문자열을 반전한 언어다.

\[L_1^R = \{ a, b, c \}\]

문자열의 길이가 1이라, 반전처리해도 같기 때문에 회문과 동일하다.

문법

• 언어를 생성하는데 사용되는 규칙들의 집합
• 형식 언어를 묘사하기 위해 존재

정규 문법

• 문자열(String)을 만들기 위해 존재
• DFA와 NFA, 정규 표현식과 동일하게, 문법은 언어를 정의하기 위해 존재한다.

• 문법 규칙 예시

  

  • 시작 기호인 S에서부터 시작하여 G1의 규칙을 따라가면 아래와 같다.
    • S ⇒ PVP ⇒ ANVP ⇒ theNVP ⇒ thecatVP ⇒ thecateatsP ⇒ thecateatsAN ⇒ thecateatsaN ⇒ thecateatsarat
    • S ⇒ PVP ⇒ ANVP ⇒ aNVP ⇒ adogVP ⇒ adoglovesP ⇒ adoglovesAN ⇒ adoglovestheN ⇒ adoglovesthecat
    • S ⇒ PVP ⇒ ANVP ⇒ theNVP ⇒ thecatVP ⇒ thecathatesP ⇒ thecathatesAN ⇒ thecathatestheN ⇒ thecathatesthedog
  • 참고로 거꾸로 적용도 가능하다.
    • PlovesP ⇒ ANlovesP
    • PlovesP ⇒ PlovesAN

• 표기 간소화가 가능하다.

  

선형 문법

• A → aB와 같은 형태는 우선형 문법(Right-Linear Grammar)이다.
• A → Bax와 같은 형태는 좌선형 문법(Left-Linear Grammar)이다.

A ⇢ bB
B ⇢ ∈/aB/bB

위 식에 해당하게 그림 그리면 아래와 같다.

정규 언어

• 정규 언어를 표현하는데는 정규 문법, DFA, NFA를 주로 사용한다.

정규 표현식

• 다양한 기호와 연산자를 사용해서 표현한다. ex) \(\Sigma, (), +, ., *\) 등이 있다.
• 기본 정규 표현식
  • f: 빈 문자열을 나타내는 정규 표현식
  • \(\lambda\): 공백 (또는 빈 문자열)을 나타내는 정규 표현식
  • a: 어떤 알파벳 기호 a를 나타내는 정규 표현식, 알파벳의 요소
• 재귀적 정의
  • **r1 + r2 또는 r1 | r2 = r1 또는 r2**를 나타내는 정규 표현식
  • **r1.r2 또는 r1r2 = r1 다음에 r2**가 오는 것을 나타내는 정규 표현식
  • **r1* = r1을 0번 이상 반복하는 것**을 나타내는 정규 표현식
  • **(r1) = 괄호를 사용하여 표현식을 그룹화**하는 정규 표현식, 이를 통해 표현식의 우선 순위를 조절 가능

  아래는 재귀적 정의의 예시들이다.

  1. 예시: a+b
     • “a” 또는 “b”를 나타냅니다. ”+”는 “또는”의 의미를 가지며, “a” 또는 “b” 중 하나를 선택하는 것을 나타냅니다.
  2. 예시:(a.b)
     • 문자열은 ‘a’로 시작하고 ‘b’로 끝나야 한다. acdb와 같은것이 있다.
     • 또 다른 예시: (a.a.b)
       • ‘a’로 시작하는 문자열 2개와 ‘b’로 끝나는 문자열이 와야한다. acacdb가 있다. 단, acadeb는 문자열 1개씩으로 친다.
  3. 예시: (ab)*
     • “ab”가 0번 이상 반복되는 것을 나타냅니다. 괄호를 사용하여 “ab”를 하나의 단위로 묶어주고 “*“을 사용하여 0번 이상의 반복을 나타냅니다. ab, abab, ababab, …..
  4. 예시: (a+b)*c
     • “a” 또는 “b”로 이루어진 문자열이 0번 이상 반복되고 그 뒤에 “c”가 오는 것을 나타냅니다. 괄호를 사용하여 “a+b”를 하나의 단위로 묶어주고 “*“을 사용하여 0번 이상의 반복을 나타냅니다.

정규 표현식을 정규 문법으로 바꾸기

정규 표현식 a(b

c)*d를 정규 문법으로 바꾸면 아래와 같다.

S -> aXd	ad
X -> bX	cX	ε

1. 시작 심볼 생성: 정규 문법의 시작 심볼 S를 생성

   S -> aXd

   ad

   여기서 S는 문자열의 시작을 의미

2. 중간 부분 생성: (b|c)를 반복하는 부분을 X로 정의

   X -> bX

   cX

   ε

   여기서 X는 b나 c를 0회 이상 반복할 수 있는 비터미널 심볼

3. 종료 부분 생성: 문자열이 d로 끝나는 경우를 처리하기 위해 S 규칙에 추가적인 선택사항을 제공

   S -> aXd

   ad

   여기서 ad는 문자열의 종료 부분을 의미

유한 상태 기계

유한 상태 오토마타

유한 상태 자동기계 즉, FA란 아래와 같다.

• 형식 언어를 인식하는 유한한 상태와 전이로 구성된 추상적인 모델이다.
• FA의 유형
  1. NFA(비결정적 유한 오토마타) - 입력에 대해 여러 상태로 전이 가능
  2. DFA(결정적 유한 오토마타) - 입력에 대해 한 가지 고유 상태로만 전이 가능

• 상태 \(Q\): \(\{q_0, q_1\}\)
• 알파벳 \(\sum\): \(\{0\}\)
• 시작상태: \(q_0\)
• 마지막 상태: \(q_1\)
• 전이함수: \(\delta(q_0, 0) = q_1\)

위 그림은 \(q_1\)에서 전이가 가능한 경우의 수가 없기 때문에 NFA다.

DFA가 되기 위해서는 아래 그림처럼 돼야 한다.

전이함수 \(\delta(q_1, 0) = q_1\)가 추가되었다.

위 그림도 \(q_0\)에서 두가지의 전이 상태가 있기 때문에 DFA다.

ε-전이

• 아무것도 입력하지 않아도 상태 q0에서 상태 q1으로 전이할 수 있다.

앱실론 전이의 예는 아래와 같다.

전이상태: \(\delta(q_0, ε) = q_1\)

앱실론은 위와 같이 어디에나 무한하게 존재할 수 있다.

\[011 = …εεε…εεε0εεε…εεεε1εεε…εεε1εεε…εεε….\]

하지만 불필요해서 생략했을뿐이다.