[CS][컴파일러의 이해] 형식 언어( formal language )

형식 언어란, 인간과 기계 사이에 의사소통을 하는 언어로서 인위적으로 만들어진 언어다.

 

📌 종류

촘스키가 제안한 촘스키 위계에 따라 형식 언어를 네 가지로 계층을 나눠 분류 할 수 있다.

1. 재귀 열거 언어( Recursively Enumerable Language, REL )

🔹 개념

• 튜링 기계에 의해 인식 될 수 있는 언어다.
• 모든 계산 가능한 문제가 포함되고, 튜링 기계가 정답을 찾을 수 있는 언어다.
• 튜링 기계가 항상 멈추는 것은 아니므로, 특정 문자열이 언어에 속하지 않는지 판별하는 것은 불가능 할 수 있다. (즉, 언어에 속하는 문자열은 확인할 수 있지만, 속하지 않는다고 확정할 수 없음)

🔹 특징

• 가장 강력한 언어 클래스로, 모든 다른 언어를 포함한다.
• 비결정적 튜링 기계로도 인식이 가능하다.
• 어떤 문자열이 언어에 속자히 않는지를 결정하는 것은 불가능 할 수 있다. ( 정지 문제와 관련 )

---

 

형식 언어 중 컴퓨터와의 의사소통에 사용되는 언어를 프로그래밍 언어( = 컴퓨터 언어 )라고 한다.

 

프로그래밍 언어는 사용 목적, 형태와 기능, 세대 등에 따라 여러 가지로 분류할 수 있다.

• 형태와 기능에 따라 저급 언어와 고급 언어로 나눈다.
  • 저급 언어에는 기계어와 어셈블리어가 있다.
  • 고급 언어에는 C, 파스칼, 코볼 등이 있다.