[개념쌓기] 오토마타 - 2

  ✔ 형식 언어의 요소와 연산 

 

1️⃣ 형식 언어

: 실제 사람이 사용하는 모호한 자연어와 달리, 정해진 형식대로 구성하여 오토마타가 인식할 수 있는 인공적인 언어

 

2️⃣ 심볼 (Symbol)

: 어떤 언어를 이루는 가장 기본적인 단위 혹은 기호

: 어떤 언어에 사용되는 기호들

 

ex) 한국어의 심볼 : ㄱ,ㄴ,ㄷ //  ㅏ, ㅑ, ㅓ, ㅕ

      영어의 심볼 : a, b, c....

3️⃣알파벳 (Alphabet)

: 심볼의 비어있지 않은, 유한한 집합

 

어떤 언어의 알파벳은 1개 이상 유한한 심볼을 포함해야 한다.

한국어의 알파벳인 한글은 자모음 40개로(표준 발음법 기준) 알파벳의 정의에 부합한다.

영어의 알파벳도 마찬가지로 26개로 알파벳의 정의에 부합한다.

 

어떤 알파벳의 심볼 집합을 표현하기 위해 이처럼 표기한다:

∑={symbol1,symbol2,…,symboln}

 

영어의 알파벳은 아래와 같이 표기 가능하다:

∑={a,b,c,d,e,…,y,z}

 

이처럼 어떤 알파벳 집합을 표현하는 기호는 ∑ 시그마를 사용합니다.

 

4️⃣ 문자열 (String)

: 그 언어의 알파벳에서 선택하여 나열한, 유한한 심볼들

 

{}

 

위와 같이 중괄호 사이에 아무것도 적혀있지 않은 경우, 아무것도 선택하지 않아도 해당 언어의 문자열로 인정한다.

어떤 알파벳에서 아무것도 선택하지 않은, 비어있는 문자열은 모든 언어의 문자열이 될 수 있다.

 

비어있는 문자열은 아무 심볼도 선택치 않아 표현할 방법이 없는데, 이러한 경우 아래의 앱실론을 통해 표현한다.

 

ε

비어있는 문자열, 앱실론은 추상적인 개념

 

👉언어 (Language)

: 어떤 알파벳 시그마 스타의 부분집합

 

👉시그마 제곱 수 (powes of an alphabet)
: 해당 알파벳 시그마에서 만들 수 있는 문자열의 집합

 

👉시그마 스타 

: 시그마 0제곱부터 시그마 제곱을 무한히 늘려가는 모든 집합의 합집합
: 어떤 알파벳 시그마로 만들 수 있는 모든 문자열의 집합

 

조금 더 딥한 개념이 있는데, 정리해놓은 개념까지는 이해가 됐으나 조금 더 깊이 갔을 때 내 이해도에 의문이 들어 추가로 정리하지는 않음

 

---

  ❗️유한 오토마타

 

오토마타는 오토마톤의 복수형으로, 어떤 기계장치를 추상화한 것을 말한다

즉, 유한 오토마타는 유한한 개수의 상태를 가지는 오토마타를 말한다.

 

유한 오토마타가 가지는 상태(state)란, 말 그대로 기계장치의 상태를 나타낸다.

사람과 달리 유한 오토마타는 임의의 시각 t에 단 하나의 상태만을 가질 수 있다.

 

유한 오토마타가 한 상태에서 다른 상태로 변하는 것은 오로지 어떠한 사건에 의해서만 가능하다.

이처럼 어느 상태에서 다른 상태로 변화하는 것을 전이(transition)라고 한다.

처음에 정리했던 하단의 링크에서 처음 유한 오토마타의 예시로 들었던 것이 스위치다.

스위치는 버튼(push)를 통해 하나의 상태만을 유지하는데, 버튼을 통해 상태가 on->off / off->on 으로 전이되는 것을 알 수 있다.

 

꼭 현재 상태와 전이 상태가 다를 필요는 없는데, 이처럼 현재 상태와 전이 상태가 같은 경우를 "자기 루프" 또는 "셀프 루프"라고 부른다.

 

---

   ❗️유한 오토마타와 형식언어의 연관성

언어는 유한, 무한한 문자열의 집합이다.

어떤 문자열이 어떤 언어에 해당하는 포함되는지 알기 위해서는 해당 언어의 원소인지를 파악해야한다.

해당 언어가 무한한 문자열을 가진다면, 문자열을 해당 언어 안에서 찾을 때까지 비교해야 하는데, 이는 거의 불가능한 행위다.  그 언어에 해당 문자열이 아예 없는 것인지, 발견이 안된 것인지 판단할 수가 없다.

 

위와 같은 상황에서 유한 오토마타가 활용된다. 유한 오토마타라는 추상적인 기계에 문자열을 입력받아서 언어에 포함된 문자열인지 판단하는 판별기 역할을 하도록 하는 것이다. 특정 언어를 인식하도록 유한 오토마톤을 설계하면, 어떤 문자열을 입력했을때 그 언어에 포함되는지 여부를 해당 오토마톤이 판단해서 반환해준다.

언어 이론에서 유한 오토마타가 어떻게 쓰이는지 위 문단과 같이 간략하게 설명할 수 있다. 

 

   언어 이론에서 유한 오토마타의 역할

1. 문자열 인식(String Recognition)
유한 오토마타는 특정 형식 언어에 속하는 문자열을 인식하는데 사용된다.

예로 언어의 문법 규칙을 유한 오토마타를 통해 특정 문자열이 그 언어에 속하는지 판별할 수 있다.

 

2. 문자열 생성(String Generation)
특정 유한 오토마타를 통해 문자열을 생성할 수 있다.

상태 전이를 따라 새로운 문자열을 형성하며, 해당 언어의 유효한 구조를 가진 문자열을 생성할 수 있다.

 

3. 언어의 정규서 검증(Regular Language Verification)

유한 오토마타는 정규 언어 표현에 사용되며, 정규 언어는 유한 오토마타로 인식 가능한 언어 중 하나다. 

언어의 정규서 검증은 유한 오토마타를 통해 확인 가능하다.

 

4. 컴파일러 이론

컴파일러는 소스 코드를 분석하고 토큰으로 나누며 문법적으로 올바른 구조를 확인하는데,

언어의 토큰화 및 문법 분석에 유한 오토마타를 활용한다.

 

5. 문자열 검색 알고리즘 

유한 오토마타는 특정 패턴이 문자열 내에서 발생하는지 검색하는데 사용되는데, KMP(Knuth-Morris-Pratt)알고리즘과 같은 문자열 검색 알고리즘에서 유한 오토마타가 중요한 역할을 한다.

 

즉, 언어 이론에서 유한 오토마타의 역할은 문자열 인식, 생성, 정규 언어 검증, 컴파일러 이론, 문자열 검색 등 다양한 용도로 활용된다.

---

유한 오토마타는 인식할 수 있는 언어가 매우 제한적인데, 유한 오토마타가 입력을 기억할 수 있는 수단이 상태(state)밖에 없기 때문이다. 이런 기억 공간의 한계 때문에, 유한 오토마타가 인식할 수 있는 언어는 한정적이다.

유한 오토마타를 인식할 수 있는 언어를 정규 언어(Regular language)라고 하며, 정규 언어는 형식 언어의 한 종류다.

 

유한 오토마타는 문자열을 입력받아, 자신이 인식하는 정규 언어에 포함되는지를 판별한다. 특정 문자열을 입력했을때 유한 오토마타가 accept하면, 그 문자열은 해당 오토마톤이 인식하는 정규 언어의 단어인 것이다.

 

---

 

양 왜 이렇게 많아;

이해할 수 있는 수준이라면서요 선생님...