유한 오토마타 Finite Automata

Automata Control unit Input file Output Storage

Automata 결정적오토마타Deterministic automata 비결정적오토마타Nondeterministic automata 인식기Accepter 변환기Transducer

결정적 유한 인식기 연산 과정이 결정적으로 진행되는 유한 인식기

결정적유한인식기 Definition2.1 M = (Q, , , q0, F) Q : 내부상태들의 유한집합  : 문자들의 유한집합이며, 입력 알파벳이라불림 : Q    Q 전체 함수이며, 전이 함수라 불림 q0Q : 초기 상태 F  Q : 종료 상태의 집합

결정적 유한 인식기 동작방식 오토마타의 초기 상태 : q0 입력 방법 : aabbaa 오토마타의 종료 : 입력의 맨 끝에 도달한 경우 승인여부 확인 : 오토마타의 종료 시점에 오토마타의 상태 체크 상태전이 : 전이 함수  에 따라 결정

전이그래프 유한 오토마타를 가시적으로 표현하기 위한 그래프 정점 : 오토마타의 상태 간선 : 오토마타에서 상태의 전이 정점의 라벨 : 상태의 이름 간선의 라벨 : 입력 심볼의 현재 값 종료상태 : 이중원으로 표시 q0 1 qf

전이그래프 (q0,a) = q1 q0 q1 a 초기상태표시

그림 2.1 1 q1 q0 q2 1 1

예제 2.1 M = ({q0, q1, q2}, {0,1}, , q0, {q1}), 전이함수  는 다음과 같다 M=(Q, , , q0, F) M = ({q0, q1, q2}, {0,1}, , q0, {q1}), 전이함수  는 다음과 같다 (q0,0) = q0 (q0,1) = q1 (q1,0) = q0 (q1,1) = q2 (q2,0) = q2 (q2,1) = q1

M = ({q0, q1, q2}, {0,1}, , q0, {q1}) (q0,0) = q0 (q0,1) = q1 1 q1 q0 q2 1 1 (q0,0) = q0 (q0,1) = q1 (q1,0) = q0 (q1,1) = q2 (q2,0) = q2 (q2,1) = q1

예제 1 q1 q0 q2 1 1 언어의 승인 여부 테스트 01, 101, 00, 0111

확장 전이함수 *: Q  *  Q : 함수의 두 번째 인수가 단일 심볼이 아닌 문자열임 *(q, ) = q, 함수가 (q0,a) = q1 이고 (q1,b) = q2 이면 *(q0,ab) = q2 *(q, ) = q, *(q, wa) = (*(q,w),a)

언어와 Dfa 정의 2.2 인식(Acceptance) 비인식(Nonacceptance) Dfa M = (Q, , , q0, F)에 의해서 인식되는 언어란 M에 대한 모든 문자열들의 집합 L(M) = {w*: *(q0, w)  F} 비인식(Nonacceptance) Dfa가 비종료 상태에서 종료 L(M) = { w  * : *(q0, w)  F}

그림 2.2 a ,b a b q1 a , b q0 q2 L(M) = { anb : n  0 }

그래프 : 전이함수 의 형식적인 논증 사용 <= 정당함을 확신할 수 있는 방법이 필요함 오토마타의 가시화 => 그래프 그래프 : 전이함수 의 형식적인 논증 사용 <= 정당함을 확신할 수 있는 방법이 필요함

정리 2.1 M = (Q, , , q0, F) : 결정적 유한 인식기 GM : 전이 그래프 모든 qi, qjQ와 w +에 대해, *(q0, w) = qj 이고 오직 그럴때에만 그래프 GM에는 라벨 w를 갖는 qi부터 qj까지의 보행이 존재한다.

증명 가정 : 길이가 n 이하인 모든 문자열 v에 대해서 참이다. 귀납단계 : 길이가 n+1인 문자열 w를 고려하자, w는 다음과 같이 표현될 수 있다. w=va *(qi, v)= qk라고 가정해 보자. 그러면 |v| =n 이므로 GM에는 라벨 v를 갖는 qi부터 qk까지의 보행이 존재하여야 한다. 이때 *(qi, w)= qj라면 오토마타 M은 전이 (qk, a)= qj 를 가져야 하며, 따라서 GM은 라벨 a를 갖는 간선 (qk, qj)를 갖게 된다. 결국, GM에는 qi와 qj사이에 라벨 va=w를 갖는 보행이 존재한다. 이 결과는 n=1일때 명확히 성립하므로, 귀납법에 따라 모든 w + 에 대해 *(qi, w)= qj라는 사실이 GM 에 라벨 w를 갖는 qi부터 qj까지의 보행이 존재한다는 것을 의미한다.

오토마타의 가시화 그래프 테이블 표현법

그림 2.3  b a q0 q0 q1 q1 q2 q2 q2 q2 q2

예제 2.3 알파벳  = {a, b}에 대한 문자열들 중 ab로 시작하는 모든 문자열들을 인식하는 결정적 유한 인식기를 구성 ab, aba, abb, ...

그림 2.4 a ,b a b q2 q0 q1 b a q3 a , b

예제 2.4 {0,1}에 대한 문자열들 가운데 부문자열 001을 포함하는 문자열을 제외한 모든 문자열을 승인하는 DFA 구성

그림 2.5 1 0,1 1 00  001 1 (00,0) = 00

연습문제 {0,1}에 대한 문자열들 가운데 부문자열 010을 포함하는 문자열을 제외한 모든 문자열을 승인하는 DFA 구성

언어군 유한오토마타 특정 언어를 인식 언어군 : 모든 가능한 유한 오토마타의 언어집합 => 정규 언어

정규언어 정의 2.3 언어 L에 대하여 L = L(M)을 만족하는 결정적 유한 인식기 M이 존재하고 오직 그럴때만 L을 정규언어라 부른다.

예제 2.5 언어 L = {awa: w  {a, b}* } 이 정규언어임을 보여라. => 언어에 대한 dfa를 찾는다.

Figure 2.6 b a q0 q2 q3 a b q1 , b

Example 2.6 L을 예제 2.5에서 주어진 언어라 하자. L2이 정규 언어임을 보여라. L2 ={aw1aaw2a :w1,w2  {a,b}*}

Figure 2.7 b b a b b a q5 a q0 q3 q4 q2 a a b q1 a , b

Example 사람 늑대 양 양배추 사람 늑대 양 양배추 M W G C

Diagram g m MWGC- WC-MG MWC-G g m w c 사람 늑대 양 양배추 M c w C-MWG W-MGC W MG-WC g m

Simulation for DFA S := q0; c := nextchar; while c  eof do s := move(s,c) c := nextchar end; if s is in F then return ‘Yes’ else return ‘No’