[공부] 형식 언어 - 언어편
잘 정의된 언어는 문장들의 집합을 정의되며 알파벳은 문장을 이루는 기본적인 Symbol로 다음과 같이 정의된다.
T : 심벌들의 유한 집합.
T1 = { ㄱ, ㄴ, ㄷ, ㄹ, ... , ㅎ, ㅏ , ㅑ , ... , ㅡ ㅣ}
T2 = { A, B, C, ... , Z, a, b, c, ... , z }
T3 = {auto, break, case, ... , while}
등등이 알파벳들의 예인데
T1은 한글에 대한 알파벳
T2는 영어를 위한 알파벳이며
T3 는 표준 C언어에 대한 알파벳이다.
알파벳 T에대한 String은 알파벳 T에 속하는 심벌이나 T에 속하는 하나이상의 심벌들을 나열한 것 이다.
T = { A } T로부터 만들수 있는 String은 A , AA , AAA, ... 등이다.
그리고 T = {a,b} 면 T로부터 만들 수 있는 String은a, b, aa, ab, bb, aaa, ... 등등이 있다.
알파벳은 보통 a, b, c, ... 과 같은 심벌들을 사용하고, 스트링을 나타내는 심벌로는 u, v, w등을 사용 한다.
w = abba 의 의미는 String w abba라는 스트링 값을 갖는다는 이야기다.
String의 길이는 심벌들의 개수이며,
면 |w| = k 이다.
String의 접속은 String을연속으로 연결 한것인데, U와 V의 접속은 u.v 로 표현하며
이면
로 표현 된다는 소리!
String의 길이가 0 인 것을 empty string이라고 하며 ε 로 표현한다.
이는
uε = u = εu
uεv = uv. 같은 속성이 있다.
|ε| = 0 이며 empty String을 λ 람다로 표현 하기도 한다.
접속 연산에 대한 ε 은 항등원 같은 역할을 한다.
a의 개수가 n개
이것은
w = apple 로 되어있다면 거꾸로
이런 꼴인것 이다.
알파벳 T에 대하여 T* 는 empty String을 포함하여 T로부터 만들 수 있는 모든 스트링의 집합이다. 또한 T+ 는 empty String을 제외한 String의 집합이다.
T+ = T* - ε 인 셈.
임의의 u, v ∈ = = T* uv ∈ T* 이다.
T에 대하여 언어 L 은 T* 의 부분 집합이다.
두 언어 L과 L' 의 곱 L * L' 은 L에 속하는 String L'에 속하는 String을 접속한 것으로 간단히 LL'로 나타낸다.
LL' = { uv| u ∈ L & v∈L' }
즉 String uv에서 prefix u 는 언어 L에속하고 suffix v는 언어 L'에 속한다.
언어의 거듭제곱은 순환적으로 다음과 같이 정의된다.
언어 L의 L* 는 다음과 같이 정의된다.
언어 L+는 다음과 같이 정의된다.
여러분들의 댓글은 큰 힘이됩니다 :)