4)언어, 문법, 오토마타 개념

언어

영어, 한국어, 중국어, 일본어등등 같은것을 자연언어라 한다.

 

알파벳: 하나 이상의 심벌들의 유한집합, ∑로 표현한다.

문자열: 심벌들의 유한길이의 순서열

ex) 알파벳은 ∑={a,b}라고 하면, aa,aba,abbba,aaaab는 알파벳 ∑에대한 문자열이 된다.특별한 경우를 제외하고, ∑는a,b,c,d...같은 소문자를 사용하고,문자열의 이름은 u,v,w...등을 사용한다.이름이 w인 문자열의 값이 aba는 w=aba라 나타낸다.

 

접합: 문자열과 문자열을 붙이는 것

ex) w=a_1a_2a_3a_4....a_n, v=b_1b_2b_3b_4...b_m 일때 w와 v의 접합 wv는 a_1a_2a_3a_4....a_nb_1b_2b_3b_4...b_m가 된다.

 

역문자열 : 문자열의 심벌들은 역순으로 배열한 것

길이: 문자열 내의 심벌의 개수. |w|로 표시한다. 그리고 심벌을 하나고 가지고 있지 않는것을 빈문자열이라 하며, λ로 표기한다. |λ|=0 이다.

 

부문자열: 문자열 w내에 존재하는 연속하는 문자열을 부문자열이라 한다. 문자열 w가 w=vu라 할때, 부문자열 v는 w의 전위부, u는 후위부라고 한다. w=aababa이라 할때, {λ,a,aa,aab,aaba,aabab,aababa}는 전위부 v의 집합이고, ababa, aba,a등은 후위부 u의 집합이 된다.

 

w^n은 문자열 w를 n번 반복한 문자열을 의미한다. 

또한 임의의 알파벳 ∑에대해 ∑에 속한 심벌들을 0개 이상 접합하여 얻어지는 모든 문자열들을의 집합을 ∑*이라 한다. 즉 ∑={a,b}라 한다면, ∑*={λ,{a,b} , {a,b}{a,b} , {a,b}{a,b}{a,b},....{a,b}^n}이 된다. 그리고 ∑*에서 λ를 제외한 집합을 ∑^+라 한다. ∑*과 ∑^+는 무한집합이다.즉 언어란 ∑*의 부분집합이며 임의의 언어 L에속하는 문자열을 언어L의 문장이라 한다.

 

언어의 역: 언어에 속하는 모든 문자열들의 역 집합. L^R이라 표기한다.

 

스타-폐포: 어떤 언어 L에 대해 L*=L^0 U L^1 U L^2...을 스타-폐포라 한다. 

양성-폐포: 어떤 언어 L의 스타폐포에서 λ를 뺀 것이다, L^+= L* - λ= L^1 U L^2 U L^3...

 

문법: 언어 정의 기법. 문법 G를 정의하면 G=(V,T,S,P)로 4가지 원소 쌍으로 정의가 된다. V는 변수라 불리는 객체들의 유한집합, T는 단말 심벌이라 불리는 객체들의 유한 집합, S는 V에 속하는 특별한 심벌, 시작변수라 한다. P는 생성규칙들의 유한집합니다.

 문법의 핵심은 생성규칙이다. 모든 생성규칙은 x->y의 형태를 갖는다고 가정한다. 이때 x는 (V U T)^+의 원소이고, y는 (V U T)*의 원소다. 문자열 w=uxv의 형태일때, 생성규칙 x->y가 적용 되면, z=uyv같은 문자열이 된다. 이런 과정을 w=>z로 표현하며 이를 w가 z를 유도한다 라고 한다. 생성규칙을 필요한 만큼 여러번 적용 될 수 있다. w_1=>w_2=>w_3=> .... =>w_n이 유도 된다면, w_1이 w_n이 유도 한다고 하며 이를  w_1 =>^* w_n이라고 표기한다.

ex) G=({S},{a,b},S,P), p={S->aSb, S->λ}라 할때, S=>aSb=> aaSbb=> aabb로 유도 할 수 있으며, S=>^* aabb로 표현 할 수 있다.

 

문법은 다르지만, 생성되는 언어가 같다면, 두 문법은 동치라고 한다.

 

오토마타: 디지털 컴퓨터에 대한 추상적 모델.