[공부] 형식 언어 - 언어편

잘 정의된 언어는 문장들의 집합을 정의되며 알파벳은 문장을 이루는 기본적인 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'에 속한다.

언어의 거듭제곱은 순환적으로 다음과 같이 정의된다.

 ( n >= 1 )

언어 L의 L* 는 다음과 같이 정의된다.

언어 L+는 다음과 같이 정의된다.

여러분들의 댓글은 큰 힘이됩니다 :)