3 - Formal Language

컴퓨터가 말하는 언어로, 정확하게 표현하기 위해 문법을 알아야 한다.
형식 언어를 이해하고 형식 문법을 이해해야 추후에 어휘를 분석할 수 있다.

 

기본 용어

---

정의 - Alphabet

Formal Language에서의 Alphabet은 
언어의 문장을 이루는 기본 심볼이다.

정의 - String 

알파벳 집합에 대한 기호들을 나열한 유한 수열으로,

{a,b,c} 일때 ccba는 string 이다.

 

 

문자열 연산

---

Length of String 

심볼의 갯수를 세는 것으로,

{a,b,c} 집합에서의 aba의 length는 3이고,

{do, case, while} 집합에서의 docase 는 length가 2이다.

 

Concatenation of String 

두개 이상의 문자열을 연결하여 문자열을 만드는 것으로,

u = a1a2a3 ... , v = b1b2b3 이면 

uv = a1a2a3..b1b2b3.. 가 된다.

식은

으로 표현한다.

 

 

공문자열

---

문자열의 길이가 0인 문자열을 나타낸다.

ϵ 표시로 나타내며 접속 연산의 항등원이다.

알파벳에 지수가 0으로 표기된 것 또한 공문자열이다.

 

 

접두사, 접미사, ∑∗

---

알파벳 ∑ 에 대해 접속 연산에 의해 만들어질 수 있는 모든 문자열의 집합이다.

 

 

 

언어 정의

---

C언어를 예로, 알파벳 모두와 언더바, 숫자가 집합으로 포함되어 있을 때 ∑∗ 가 변수명으로 정해지지 않는다.

숫자가 앞으로 왔을때 (예 : 123_a) 와 같은 변수명은 예외를 시켜줘야 하기 때문에

∑∗ 에 조건을 걸어야 한다.

조건을 거치고 난 뒤 집합을 language L이라고 한다.

L도 마찬가지로 일어날 수 있는 모든 경우의 수를 L∗, L+로 나타낼 수 있다.