[컴공] 형식언어 입문

1. 형식언어의 개념

형식언어는 수학적이고 형식적인 체계를 이용하여 인간이 사용하는 자연어와 구별되는 형식을 갖춘 언어로 정의된다. 형식언어는 표현의 명확성과 엄격성을 확보하기 위해 문법과 의미를 엄격하게 규정하며, 주로 컴퓨터 과학에서 언어의 구조를 분석하고 설계하는 기초로 사용된다. 예를 들어, 프로그래밍 언어는 형식언어의 한 종류로서, 구문과 의미 규칙이 정해져 있어 인간이 이해하는 자연어와 달리 컴퓨터가 명령을 정확히 수행할 수 있게 한다. 형식언어는 일반적으로 알파벳 집합, 생성 규칙, 문법 세 가지 구성요소로 이루어져 있다. 알파벳은 유한한 기호 집합이며, 생성 규칙은 알파벳과 문법 기호들을 사용하여 유효한 문자열을 만들어내는 규칙이다. 문법은 이 규칙들을 통해 어떤 문자열이 언어에 속하는지 판단하는 구조로서, 문법의 엄격성에 따라 언어의 종류가 결정된다. 본질적으로 형식언어는 형식적 시스템의 표현으로, 예를 들어 정규언어, 문맥 자유언어, 문맥 민감언어, 튜링 머신 가능 언어 등으로 분류되며 각각의 언어는 인지 처리 능력과 계산 능력에 따라 차이를 보인다. 특히, 2020년 기준 세계 컴퓨터 과학 연구논문 …