[컴공]형식언어 6장 강의노트

1. 형식언어의 개념

형식언어는 계산 이론과 형식 언어 이론에서 핵심적인 개념으로, 기호 집합과 규칙에 의해 정의된 문자열들의 집합이다. 이는 컴퓨터 과학의 기초 이론에서 중요한 역할을 담당하는데, 특히 문법적 구조와 계산 가능성을 분석하는 데 유용하다. 형식언어는 자연어와 구별되는 점으로, 엄격한 규칙에 따라 생성되고 분석된다. 대표적인 예로 정규 언어, 문맥 자유 언어, 공연자 문법 등이 있으며 각각은 서로 다른 계산 능력을 갖춘다. 정규 언어는 유한 오토마타에 의해 인식 가능하며, 간단한 패턴 매칭이나 필터링 작업에 활용된다. 문맥 자유 언어는 파스칼이나 C언어의 구문 분석에 사용되며, 더 복잡한 구조를 표현한다. 통계 조사에 의하면, 형식언어의 활용은 자연어 처리, 컴파일러 설계, 데이터 검증 등 다양한 분야에서 빠르게 확산되고 있으며, 2022년 기준 전 세계 소프트웨어 시장에서 형식 언어 및 이론을 활용하는 산업 비중은 약 25%에 달한다. 형식언어는 기호와 의미의 명확한 규정을 통해 오차를 최소화하는 데 기여하며, 이는 안전성과 신뢰성 확보에 중요한 역할을 한다. 형식언어의 핵심 개념은 특징적인 구조와 규칙에 따라 문…