[컴공] fl(형식언어) 1장 강의노트

1. 형식언어 개요

형식언어는 계산 이론과 컴퓨터 과학의 핵심 개념으로, 문자열들의 집합을 수학적으로 규정하고 분석하는 분야이다. 형식언어는 일반적으로 문자 집합인 알파벳에 대한 규칙에 따라 특정 조건을 만족하는 문자열들의 집합이다. 이러한 언어는 자연어와 달리 엄격한 문법과 규칙을 가지고 있으며, 이를 통해 컴퓨터가 이해하고 처리할 수 있는 형식을 만든다. 형식언어는 크게 무한한 문자열 집합이면서도 정규언어, 문맥 자유언어, 문맥 민감언어, 재귀언어와 같은 계층으로 분류되며, 이는 각각의 복잡도와 표현력을 나타낸다. 예를 들어, 정규언어는 간단한 패턴 매칭이나 문자열 검증에 적합하며, 정규 표현식을 통해 쉽게 표현될 수 있어 현대 프로그래밍 언어, 검색 엔진, 텍스트 분석에서 널리 사용되고 있다. 2020년 기준으로 전 세계 인터넷 검색 요청의 65% 이상이 정규 표현식을 활용하는 것으로 보고되어 있으며, 이는 정규언어의 실용성과 중요성을 보여준다. 형식언어의 중요한 목적은 언어의 문법적 구조를 명확히 규정하여 컴퓨터가 자동으로 언어를 분석하고 효율적으로 수행할 수 있게 하는 것이다. 예를 들어, 컴파일러가 소스 코드를 …