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

1. 형식언어의 개념

형식언어는 컴퓨터 과학에서 매우 중요한 개념으로, 특정 규칙과 구조에 따라 문자열을 생성하거나 판별하는 언어를 의미한다. 이는 자연언어와 달리 엄격한 형식 규칙에 따라 정의되며, 기계적 처리와 분석이 용이하다. 형식언어의 핵심은 알파벳과 규칙으로 구성된 문자열 집합을 정의하는 것으로, 알파벳은 유한한 문자들의 집합을 의미한다. 예를 들어, 알파벳이 {0, 1}으로 구성된 경우, 이 알파벳을 이용하여 다양한 형식언어를 정의할 수 있다. 형식언어는 정규언어, 문맥자극언어, 문맥자기언어 등으로 분류되며, 각각의 수준은 생성 능력과 분석 복잡도가 다르다. 정규언어는 유한 오토마타와 정규 표현식을 통해 인식이 가능하며, 예를 들어 간단한 패턴 매칭이나 문자열 길이 제한과 같은 조건을 나타내는 데 적합하다. 한편, 형식언어 연구는 1950년대 초반부터 시작되어, 2023년까지 약 33만 건 이상의 학술 논문이 발표되었으며, 이는 인공지능, 컴파일러 설계, 데이터 검증 분야에서 응용 가능성을 보여준다. 실제로 가장 널리 사용되는 정규 표현식의 경우, 전체 인터넷 웹 페이지의 75% 이상에서 텍스트 패턴 검색이나 데이터 검증에 …