CS/오토마타

[오토마타] 3. 오토마톤

2024. 10. 17. 14:44
목차
  1. 오토마톤 적용
반응형

 

오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.

디지털 컴퓨터는 기본적으로 입력이 주어지면 저장공간을 활용하여 이를 적절히 처리한 뒤 결과물을 내보낸다.

 

이때 입력 데이터는 수학적 편의를 위해서 '알파벳 심볼에 의해 정의된 문자열' 이라고 정의한다. (꼭 이래야만 하는 것은 아니다)

그리고 인풋 파일은 무한한 길이의 테이프로부터 문자열을 읽어들일 수 있다고 생각한다.

이 테이프는 여러개의 셀로 구성되어 있으며, 각 셀에는 알파벳 심볼 하나가 저장된다.

 

디지털 컴퓨터는 내부적으로 연속된 시간이 아니라, 이산적인 시간 체계로 동작하며,

각 시간마다 인풋 파일의 왼쪽에서 오른쪽을 향해 한번에 하나의 셀(심볼)을 읽어들인다.

그리고 End-Of-File (EOF) 신호를 통해 문자열의 끝을 감지할 수 있도록 기계가 만들어져 있다고 하자.

 

이 기계는 temporary storage를 갖는데, 이 저장 공간은 크기가 무한하다고 가정한다.

그리고 인풋 파일처럼 여러 개의 셀로 이루어져 있으며, 이 공간에 대해서는 값을 읽을 수도, 수정할 수도 있다.

(화살표가 인풋 파일과 달리 양방향이다.)

 

입력 데이터를 처리하는 control unit 의 경우, 내부적으로 유한한 상태(state)를 갖는다.

컴퓨터가 꺼져있다가 켜지면, 초기 상태에서 출발해서 이산적인 시간이 흐름에 따라 다른 상태로 변화할 수 있다.

또한 상태를 갖는다는 것은 내부적으로 별도의 저장공간을 갖고 있음을 의미한다.

 

 

이를 기반으로 transition function 을 생각할 수 있다.

트랜지션 함수는 특정 시점에서의 contorl unit의 상태, input symbol, storage 정보가 주어질 때 어떤 상태로 변화하는지 / 스토리지 값을 어떻게 바꾸는지 기술한 함수이다.

 

그리고 이 시점에서의 제어유닛 상태, 인풋 심볼, 저장공간 정보를 묶어서 Configuration 이라고 한다.

마지막으로 Configuration 에서 다른 Configuration으로 변화하는 것을 Move 라고 한다.

 

오토마톤 기계는 다양한 기준에 따라 분류할 수 있다.

 

먼저 특정 상태에서의 Move 개수에 따라

결정적인 (Deterministic) 기계는 Move 가 유일하고,

비결정적인 (Non-Deterministic) 기계는 다양한 Move 가 있을 수 있다.

 

기계의 출력에 따라서는

만약 출력이 이진화되어있다면 Acceptor 라고 하고, (yes / no 로 대답하는 경우)

출력이 string으로 다양하게 나온다면 Transducer 라고 부른다.

 

 

 


오토마톤 적용

C언어에서는 다음과 같은 규칙의 문법이 있다.

 

식별자는 문자, 숫자, _ 의 나열인데, 숫자로는 시작할 수 없고, 대소문자를 모두 사용할 수 있다고 한다.

그렇다면 자연어로 기술된 이 규칙을 지난 글에서 정리한 Grammar로 어떻게 나타낼 수 있을까?

프로그래밍언어론에서 정리했던 BNF 규칙처럼 다음과 같은 문법으로 나타낼 수 있다.

 

 

이 문법은 C언어 식별자의 productions 를 보여준다.

여기에서 < > 안에 들어있는 문자열은 모두 '변수'를 의미한다.

그리고 < > 로 감싸져있지 않은 문자열은 모두 '터미널' 이다.

특히 <id> 는 start variable 이다.

 

이 문법을 이번 글에서 정리한 오토마톤을 사용해 나타내면 위와 같이 나타낼 수 있다.

 

 

 

동그라미는 '상태' 를 나태내고, 각 화살표는 상태의 이동을 나타낸다.

화살표 위의 문자는 그 상태로 변화하는 조건(그 순간의 input symbol)을 나타낸다.

 

1번 상태는 들어오는 화살표가 하나 있는데, 이 기호는 1번 상태가 초기 상태임을 나타낸다.

1번 상태에서 숫자가 들어오면 3번 상태로 가고, 문자나 _ 가 들어오면 2번 상태로 간다.

그리고 2, 3번 상태에서는 어떤 입력이 들어와도 현재 상태를 유지한다.

 

이 기계는 최종적으로는 내 현재 상태가 2번 변수명이 맞다고 대답하고, 1 또는 3이면 변수명이 아니라고 대답하는 기계가 된다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > 오토마타' 카테고리의 다른 글

[오토마타] 6. FA 에서 state 개수 줄이기  (0) 2024.10.22
[오토마타] 5. NFA (Nondeterministic Finite Accepter)  (0) 2024.10.20
[오토마타] 4. DFA (Deterministic Finite Accepter)  (0) 2024.10.17
[오토마타] 2. Language, Grammar  (0) 2024.10.14
[오토마타] 1. 기본적인 수학적인 지식  (1) 2024.10.12
  1. 오토마톤 적용
'CS/오토마타' 카테고리의 다른 글
  • [오토마타] 5. NFA (Nondeterministic Finite Accepter)
  • [오토마타] 4. DFA (Deterministic Finite Accepter)
  • [오토마타] 2. Language, Grammar
  • [오토마타] 1. 기본적인 수학적인 지식
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (591) N
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (315) N
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (15) N
      • 기계학습심화 (12)
    • 자기계발 (36) N
      • 동아리 (7)
      • 자격증 (2)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (18) N
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[오토마타] 3. 오토마톤
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.