시작은 정규표현식에 대한 궁금증에서 시작된다.
정규표현식을 크나큰 생각없이 사용하다가, 이게 무엇이길래? 여러 언어들에서 통용되고 있는것일까? 라는 생각이 들었다.

그래서 두권의 책을 구매하고, 기록을 남기기로 했다.

정규표현식 - 예스24

신야 료마,스즈키 유스케,타카타 켄 공저/김완섭 역. 제이펍. 판매가 23,400원(10% 할인). 포인트 1,300원(5% 적립). 최신 엔진 구현과 이론적 배경!한 권으로 배우는 정규표현식의 모든 것!문자열 패턴을 간단한 식으로 기술할 수 있는 정규표현식은...

https://www.yes24.com/Product/Goods/24521492

형식언어와 오토마타 - 예스24

Peter Linz 저/김응모,엄영식,박희진,배상원 공역. 홍릉. 판매가 35,000원. 이 책은 컴퓨터 프로그래밍의 형식언어와 오토마타에 대해 다룬 도서입니다. 형식언어와 오토마타의 기초적이고 전반적인 내용을 학습할 수 있도록 구성했다.

https://www.yes24.com/Product/Goods/95877099

정규표현식 어디서 왔는가?

정규표현식에 도달하기 전에, 태초의 질문이 있었다.

계산이란 무엇인가?

정규표현식이 탄생하기 전까지 이 질문에 대한 해답을 찾기 위한 여러 시도가 있었다. 그 과정에서 ‘계산이론’ 이라는 분야가 생겨나게 되었다.

1930년대 앨런 튜링은 이러한 질문에 대한 해답을 찾기 위해 ‘튜링머신’을 고안했다. On Computable Numbers, with an Application to the Entscheidungsproblem ‘계산 가능한 숫자에 대하여, 결정 문제(Entscheidungsproblem)에의 응용을 포함하여’라는 논문을 통해 ‘튜링머신’을 제안했고. ‘계산할 수 있는 것’ 이라는 정의를 ‘튜링머신을 통해 계산할 수 있는 것’ 이라는 정형화된 개념으로 바꾸었다.

튜링 머신에 대해서는 각자 찾아보자.

시간이 흘러 1940년대 워런 맥컬록과 월터 피츠는 ‘신경세포’를 모델로 한 ‘형식적 뉴런’을 제안했다. A Logical Calculus of the Ideas Immanent in Nervous Activity ‘신경 활동에 내재된 아이디어의 논리 계산’

머신러닝 강의에서 ‘퍼셉트론’에 대해서 들어본적이 있을 것이다. 퍼셉트론은 ‘형식적 뉴런’을 모델로 한 인공신경망의 한 종류이다. 입력값과 가중치, 그리고 활성화 함수를 통해 출력값을 계산하는 구조를 가지고 있다.

도표를 첨부할 것

형식적 뉴론은 ‘논리 게이트’를 통해 계산을 수행한다. 하지만 튜링머신처럼 모든 계산을 수행할 수 없다. 이 둘 사이에는 기억 영역의 차이가 있다.

튜링머신은 테이프를 통해 무한한 메모리를 가지고 있지만, 형식적 뉴론은 기억 영역이 없다. 그럼 그런 기억 영역이 없는 형식적 뉴론을 통해 어떤 계산을 수행할 수 있을까?

시간이 다시 흘러 1950년대, 스티븐 클레이니가 이러한 질문에 대한 해답을 찾았다. Representation of Events in Nerve Nets and Finite Automata ‘신경망과 유한 오토마타에서의 사건 표현’

이 논문을 통해서 ‘정규표현식 Regular Expression’이라는 표현을 제안했고, 형식적 뉴런을 통해 계산할 수 있는 것은 정규표현식으로 표현할 수 있다는 것을 보여주었다.

그리고 정규표현식에 이어서 ‘유한 오토마타’라는 ‘계산 모델’을 제안했다.

유한 오토마타(finite accepter)

기억 영역이 없는 형식적 뉴론과 같이, 유한 오토마타도 기억 영역이 없는 계산 모델이다. 즉, 기억 영역 없이 계산을 수행할 수 있는 것에 대한 계산모델이다.

같은 의미로, 메모리 필요 없이 계산을 수행할 수 있는 모델이라고 할 수 있다.

이제 유한 오토마타에 대해서 알아보자.

유한 인식기(finite accepter) 에 대해서 설명

유한 인식기는 유한 개수의 상태를 가지며, 그 외의 다른 기억 장소를 가지지 않기 때문에 유한하다고 한다.
또한 상태가 승인(accept) 아니면 거부(reject) 이기 때문에 인식기라고도 한다.
그중에서도 결정적 유한 인식기 dfa(deterministic finite accepter)는 정규 언어를 위해 사용된다.

결정적 유한 인식기 DFA _ Deterministic Finite Accepter

동작 방식

초기 상태 q_0 가 있는 것으로 가정,
입력 장치는 입력 문자열의 가장 왼쪽 심벌에 놓여있다.
오토마타는 매 이동마다, 입력장치는 한 자리씩 오른쪽으로 이동. (하나씩 읽어온다)
맨 끝에 도달했을 때, 오토마타가 승인 상태에 있으면, 해당 문자열 승인(accept)
그렇지 않으면 거부(reject)
전이는 전이함수 δ에 따라 결정된다.
예를 들어 δ(q_0, a) = q_1라는 전이가 있고, dfa 상태가 q_0에 있고, 현재 입력 심벌이 a인 경우 q1으로 전이 할 것이다.
이를 가시적으로 표현 한 것이 전이 그래프(transition graph)
승인 상태는 이중원으로 표현한다.

예제 1

$M = (\{q0, q1, q2\}, \{0,1\}, δ,q_0,\{q_1\})$

$δ(q_0,0)=q_0, δ(q_0,1)=q1$
$δ(q_1,0)=q_0, δ(q_1,1)=q2$
$δ(q_2,0)=q_2, δ(q_2,1)=q1$

stateDiagram-v2
		direction LR
		classDef Accept stroke-width:3px
    state q0
		state q1
		state q2
    [*] --> q0
		q0 --> q0 : 0
		q0 --> q1 : 1
		q1 --> q0 : 0
		q1 --> q2 : 1
		q2 --> q1 : 1
		q2 --> q2 : 0

		class q1 Accept

이 DFA는 01은 승인하지만, 11, 100, 1100 등은 승인 하지 않는다.

확장 전이 함수 (Extended Transition Function)

$δ^*={Q}\times{Σ^*}\to{Q}$

δ^* 의 두번째 인수는 단일 심벌이 아닌 문자열
함수 값은 오토마타가 주어진 문자열을 모두 읽은 후에 놓이게 되는 상태

$δ(q_0,a) = q_1 이고 δ(q_1, b)=q2이면$
$δ^*(q_0,ab)=q_2이다.$

언어와 결정적 유한 인식기

언어란 주어진 오토마타에 의해서 승인되는 모든 문자열 집합
DFA M에 의해 인식되는 언어란, M에 의해 승인되는 Σ에 대한 모든 문자열의 집합

$L(M) = \{w\inΣ^*:δ^*(q_0,w)\in{F})$

${w∈Σ^*}$ : 이 부분은 $Σ^*$ 에 속하는 모든 문자열 w의 집합을 의미합니다. 여기서 Σ는 오토마타의 입력 알파벳이고, Σ^*는 Σ에서 만들 수 있는 모든 가능한 문자열들의 집합을 의미합니다. 예를 들어, 만약 Σ = 1이라면, Σ^*는 "", “0”, “1”, “00”, “01”, “10”, “11”, “000”, “001”, … 등 모든 가능한 이진 문자열들의 집합
$δ^*(q_0,w)∈F$ : 이 부분은 문자열 w를 읽은 후에 DFA가 최종적으로 도달하는 상태가 승인 상태 집합 F에 속한다는 것을 나타냅니다. 여기서 δ^*는 확장 전이 함수로, q_0에서 시작해서 문자열 w를 읽은 후에 오토마타가 놓이게 되는 상태를 나타냅니다.

따라서, 전체 식 $L(M) = {w∈Σ^*: δ^*(q_0,w)∈F}$ 는 “DFA M이 인식하는 언어 $L(M)는 Σ^*$ 에 속하는 모든 문자열 w 중에서, w를 읽고 나서 M이 승인 상태에 도달하는 모든 문자열 w의 집합”을 의미합니다.

승인되지 않는 집합
$\overline{L(M)}=\{w∈Σ^∗:δ^∗(q0,w)\notin{F}\}$
모든 문자열 집합중에서 최종 승인상태에 속하지 못하는 요소들

정규언어

모든 유한 오토마타는 특정 언어를 인식
유한 오토마타는 마치 언어를 인식하는 기계처럼 작동합니다. 예를 들어, 어떤 기계는 “안녕”이라는 단어만 인식할 수 있을 것이고, 다른 기계는 “안녕하세요”만을 인식할 수 있을 것
모든 가능한 유한 오토마타들을 고려해보면 이들과 관련된 언어들의 집합을 얻을 수 있음. 이러한 언어의 집합을 언어군(family)라고 부른다.\

결정적 유한 오토마타에 의해 인식되는 언어군은 극히 제한적.

예제) L이 정규언어임을 보여라

$L =\{ awa: w \in \{a,b\}^*\}$

$δ(q_0,a)=q_2$
$δ(q_0,b)=q_1$
$δ(q_2,b)=q_2$
$δ(q_2,a)=q_3$
$δ(q_3,b)=q_2$
$δ(q_3,a)=q_3$ \

stateDiagram-v2
		direction LR
		classDef Accept stroke-width:3px
    state q0
		state q1
		state q2
		state q3
    [*] --> q0
		q0 --> q2 : a
		q0 --> q1 : b
		q1 --> q1 : a, b
		q2 --> q2 : b
		q2 --> q3 : a
		q3 --> q2 : b
		q3 --> q3 : a

		class q3 Accept

언어 L은 ${a,b}$ 에 속하는 w 앞뒤로 a가 오는 문자열의 집합이다. 이는 위와 같은 DFA로 표현되며 그렇기에 정규언어라고 할 수 있다.

정규언어가 아닌 경우

팔린드롬 언어: $L1={w|w는 팔린드롬}$ 이 언어는 앞에서 읽으나 뒤에서 읽으나 같은 문자열(팔린드롬)로 구성되어 있습니다. 예를 들어, “abba”, “madam”, “a”, “aa” 등은 이 언어에 포함되지만 “ab”, “abc”는 포함되지 않습니다. DFA만으로는 중간 지점을 정확히 알아내고 뒤집힌 문자열을 비교하는 것이 불가능합니다.
포맷 매칭 언어: $L2={a^nb^n|n≥0}$ 이 언어는 ‘a’가 n번, 그 다음에 ‘b’가 n번 오는 문자열들로 구성됩니다. 예를 들어, “ab”, “aabb”, “aaabbb” 등은 이 언어에 포함되지만, “aab”, “aba”, “aaabb”는 포함되지 않습니다. 이는 DFA가 ‘a’의 정확한 수를 세고, 그 다음에 같은 수의 ‘b’를 확인하는 것이 불가능하기 때문입니다.

반대 언어: $L3={ww|*∈{a,b}*}$ 문자열 w 뒤에 동일한 문자열 w가 오는 경우의 집합입니다. 예를 들어, “aabbcc”, “aabc”, “bbb” 등은 포함되지 않지만 “aabaab”, “aaa”, “babbab”는 포함됩니다. DFA로 문자열의 반복 부분을 정확하게 파악하고 인식하는 것은 어렵습니다.

DFA는 현재 상태만 기억할 수 있고, 과거 입력이나 미래 입력에 대한 정보는 기억할 수 없다.