1.2 형식언어
[형식언어 기초]
- 형식언어 ( formal language ) : 어떤 알파벳에서 얻은 기호(symbol)들로 구성되는 문자열들의 집합
- 알파벳 : 기호들의 유한집합
- 문자열 : 알파벳을 구성하는 기호가 0개 또는 1개 이상 나열된 것
ex ) 집합 T = { a, b, c}가 주어졌을 때, 집합 T는 기호 a, b, c들의 집합이므로 알파벳이다.
T로부터 만들어지는 문자열은 a, b, c, ab, ac, ca,..... 등이다.
- 문자열의 길이 : 문자열을 이루는 기호들의 갯수를 문자열의 길이라고 한다. |w|로 표시한다.
ex) w1 = abc, w2 = abab 의 문자열에 대한 길이는 |w1| = 3 , |w2| = 4라고 할 수 있다. - 공문자열 : 문자열의 길이가 0 인것을 공문자열이라고 한다. ε 로 표시한다. ( 그리스어 앱실론을 의미 )
- T* : 알파벳 T에 대해서 공문자열을 포함한 T에 속하는 기호들로 이루어질 수 있는 모든 문자열의 집합을 의미한다. T스타 혹은 T클로저로 읽는다.
- T＋: T*에서 공문자열을 제외한 모든 문자열의 집합을 나타내며 T대거라고 읽는다.
ex ) T = { a, b, c } T* = { ε, a, b, c, ab, ac, ba, ca , ......... } => 공문자열 ε을 포함한 문자열의 집합 T+ = { a, b, c, ab, ac, ba, ca , ......... } => 공문자열 ε을 제외한 문자열의 집합
[형식문법]
- 형식문법 : 형식언어를 생성하기 위한 규칙
ex) 그림 1 - 논터미널 기호 : 언어에서 문자열을 생성하는데 사용되는 중간과정의 기호로 보통 대문자로 표시한다.
- 터미널 기호 : 정의된 언어의 알파벳이나 기호로 영문자의 소문자나 아라비아숫자, 연산자 기호 등이 여기에 속한다.
- 문법기호 : 터미널기호와 논터미널 기호를 문법기호 ( grammar symbol )라고 하며 보통 V(vocabulary)료 표시한다.
< 논터미널 기호 >
1). A, B, C와 같은 영문 대문자로 구성된 기호와 시작기호를 나타내는 S는 논터미널기호
2). '<' 와 '>' 묶어서 나타낸 기호도 논터미널기호
<터미널기호>
1). a, b, c와 같은 영문 소문자로 구성된 기호 혹은 +, - 와 같은 연산자기호, 괄호나 쉼표와 같은 구분자
0, 1, 2와 같은 아라비사 숫자는 터미널기호
2). 영문자 끝 부분의 소문자인 u, v, w, x, y, z 등은 터미널기호로 이루어진 문자열을 나타낸다.
<문법기호>
1). X, Y, Z와 같은 영문자 끝부분의 대문자는 터미널 기호와 논터미널 기호를 나타내는 문법기호다.
2). α, β, γ와 같은 그리스어 소문자는 문법기호로 구성된 문자열을 나타낸다.
<시작기호>
1). 아무런 언급이 없으면 첫 번째 생성규칙의 왼쪽에 있는 기호가 시작기호다.
ex)
문법 G = ({S, A}, {0,1}, P, S)
- S와 A는 논터미널기호
- 0과 1은 터미널 기호
- S는 시작기호 - 맨좌측에 있기 때문
[촙스키 계층구조]
생성규칙의 형태에 가해지는 제한에 따라 type0, type1, type2, type3의 4종류로 나눈 것
- 모든 문법은 type0에 속한다.
- type0에서 위축형 생성규칙을 제거하면 type1 -> 줄어들지 않는 문법
- type1에서 왼편이, 하나의 논터미널기호인 경우를 type2
- type2에서 오른편 생성규칙이 좌선형이거나 우선형인 경우를 만족하면 type3
- 각각의 문법은 다음과 같은 포함관계를 갖는다.
[문법, 언어, 인식기]
문법이 주어지면 그 문법에 맞는 언어를 생성할 수 있는데,
정규 문법에 의해서 생성될 수 있는 언어를 정규언어라 하고
context-free 문법에 의해 생성될 수 있는 언어를 context-free 언어
context-sensitive 문법에 의해 생성되는 언어를 context-sensitvie 언어라 한다.
이러한 언어들은 그 언어를 인식할 수 있는 기계가 필요하며 이를 인식기 ( recognizer )라고 한다.
