[컴공] 형식언어입문(FL) 3장 강의 노트

1. 형식언어의 기본 개념

형식언어는 컴퓨터 과학에서 중요한 기초 개념으로, 특정 문자집합으로 이루어진 문자열들의 집합을 의미한다. 이러한 언어는 자연언어와 구별되며, 형식언어는 명확한 규칙과 문법에 따라 생성되고 분석될 수 있기 때문에 컴파일러 설계, 정적 분석, 자동 증명 등 다양한 분야에서 핵심적인 역할을 한다. 형식언어는 보통 문자집합, 즉 알파벳으로 구성되며, 이 알파벳 위에 작용하는 문법과 규칙으로 언어를 정의한다. 예를 들어, 프로그래밍 언어의 문법은 정규형식, 문서의 구조적 태그, 수학적 표현 등 다양한 형식언어로 기술된다. 형식언어는 집합으로 생각할 수 있는데, 예를 들어 자연수의 집합 N 혹은 유한집합 {a, b, c}로 이루어진 문자열들, 그리고 이 문자열들을 정리하는 규칙들이 그것이다. 구체적으로, 정규언어는 유한 개의 규칙으로 생성된 문자열들의 집합이고, 문맥 자유언어는 문법 규칙들이 재귀적이거나 계층적인 구조를 갖는 특징이 있다. 통계 자료에 따르면, 2022년 기준 기업에서 개발하는 소프트웨어의 78%가 형식언어를 기반으로 설계된 컴파일러와 파서, 검증도구를 사용하며, 이는 형식언어의 신뢰성과 효율성을 …