기호, 의미, 계산 (Syntax, Semantics, Computation)

기호 (Syntax)에 의한 형식 언어

 

언어는 기호(시그마로 표기)로 이루어진 스트링의 집합으로 구성이 됩니다.

 

형식 언어(Formal Language)는, 모든 원하는 스트링이 빠짐없이 포함되고, 불필요한 스트링이 첨가되지 않는 것으로, 그 과정에서 집합(Set)이나 연산자(Set Operation)을 사용하게 됩니다.

 

ex) Language L1, L2가 있을 때, L1 ∩ L2, L1 U L2, L1 - L2 등등의 Set Operation을 활용하여 새로운 Language를 정의할 수 있습니다.

 

현재 컴퓨터에서 사용하는 모든 언어는 형식 언어가 사용되고 있습니다.

 

언어는 제일 단순한 형태인 정규 언어(Regular Language)와 정규 언어에서 두 문자의 발생 빈도 수가 연관되는 문맥 자유 언어(Context-Free Language)가 있습니다.

 

프로그래밍 언어는 Context-Free Language로, 언어의 문법(Grammar)또한, Context-Free 구조를 가집니다.

 

의미 (Semantics)

기호는 의미의 표현이므로, 모든 기호는 그 의미와 연관시킬 수 있어야하는데, 만일 하나의 스트링이 의미를 여러개를 가지는 상황이 생기면 해당 상황을 Formal Language에서는 이런 모호한(ambiguous)상황을 허락하지 않기 때문에, 수학적인 방법으로 구분합니다.

 

ex) String "11"은 Decimal로 11이지만, Binary로는 3입니다. 즉, String "11"은 의미가 2가지 이상을 가지고 있으므로, 프로그래밍 언어로 사용하기에 모호합니다. 따라서, "11"을 "0b11"로 표현합니다.

 

계산 (Computation)

스트링들을 기계적으로 계산하기 위해서 여러 모델들을 사용합니다.

 

Regular Language의 인식 및 계산을 위해서 유한 오토마타 (Finite Automata) 를 사용하고, Context-Free Language의 인식 및 계산을 위해서는 문자의 발생 빈도 수 연관을 위해 Stack Memory를 사용해야 하므로 푸쉬다운 오토마타 (Push-down Automata) 를 사용합니다.

 

그리고 Universal Abstract Machine으로 튜링 머신(Turing Machine)이 있습니다.

추후 포스트 하겠지만, 튜링 머신의 경우, 양방향 메모리를 가지고 있으며, 계산 과정이 알고리즘으로 표현 가능한 모델로 현대 컴퓨터의 구현 모델입니다.