소프트웨어 엔지니어를 위한 Lean 형식 증명 완전 분석
Key Point
형식 증명은 프로그램처럼 작성되어 컴파일되므로, 이 사례는 소프트웨어 엔지니어가 타입 검사와 증명 보조기의 관계를 이해하고 실제 이론 문제에 어떻게 적용하는지 구체적으로 배울 수 있다.
핵심 요약
- 소프트웨어 엔지니어 입장에서 형식 증명이 무엇인지 이해하기 위해 Lean을 이용해 결정적 유한 오토마타(DFA) 이론 문제를 증명한 과정을 설명한다.
- 계산 이론 교재의 문제: 세 행의 비트 문자열(최상단 + 중간 = 최하단)에서 덧셈이 성립하는지 검증하는 언어 B가 정규언어임을 증명하는 것이었다.
- 정규언어의 폐쇄성을 이용해 B의 역순 B^R을 인식하는 DFA를 구성하면, B^R이 정규이므로 그 역순인 B도 정규임을 결론 낼 수 있다.