Tel : 850-7288 Office : 2공학관 408호 E-mail : kim@kiu.ac.kr 오토마타 및 형식언어 김 현 성 Tel : 850-7288 Office : 2공학관 408호 E-mail : kim@kiu.ac.kr

사람의 언어 1더하기 2는 뭐야? 뭐라고?

컴퓨터의 언어 1+2=? 100 001 010 프로그래밍 언어 3 011

Three Basic Concepts(1/2) Languages Grammars Automata

Automata(1/2) Abstract model of a digital computer Input file Storage Control unit Output

Automata(2/2) 1 q1 q0 q2 1 1

Three Basic Concepts(2/2) Languages Grammars Automata

Grammar, Languages, Recognizer Grammar Language Recognizer Type 0 recursively enumerable sets Turing machine Type 1 context-sensitive language Linear bounded automata Type 2 context-free language Pushdown automata Type 3 regular language Finite automata

Chomsky’s Language Hierarchy Regular Languages Context-free Languages Context-sensitive Languages Unrestricted Languages

Applied Area Compiler Digital Design Finite Automata lexical analysis (parser) Digital Design binary adder

계산이론개요

목적 컴퓨터 공학 분야에는 몇 가지 공통적인 기본 원리가 존재 기본 원리를 이해하기 위해서는 추상적 모델을 설정해야 한다 추상적 모델 => 하드웨어 및 소프트웨어에서 공통적으로 나타나는 특징들을 표현하기 위한 모델

목적 추상적 모델 => 오토마타 오토마타는 입력, 출력, 기억장소로 구성 형식언어는 프로그래밍언어들의 일반적인 특성들을 추상화한 개념 형식언어는 심볼들과 심볼들의 조합인 문장을 구성하는 형식규칙들의 집합 형식언어는 이 형성규칙들에 의해 생성되는 모든 문자열들의 집합

한국어 우리는 경일대인이다. 경일대인은 나다.

목적 개념탐구 방법 직관적인 방법 수학적인 방법 집합론 함수 관계 트리 그래프

함수(1/2) 함수란 한 집합의 원소들 각각에 대해 다른 집합의 유일한 원소로 배정하는 규칙 F : S1 S2 domain range S1 S2

함수(2/2) 함수의 표현 {(x1,y1),(x2,y2),…} xi : 해당함수의 정의역의 원소 domain range 함수(2/2) 함수의 표현 {(x1,y1),(x2,y2),…} xi : 해당함수의 정의역의 원소 yi : 해당함수의 치역의 대응값 각 xi가 이 집합 내에서 순서쌍의 첫 번째 위치에 최대 한번만 나타나야 한다. X Y

오토마타 1 q1 q0 q2 1 1

그래프 (1/2) 그래프는 두개의 유한집합으로 구성된 구조 정점들의 집합the set of vertices 간선들의 집합the set of edges 간선들의 순서열a sequence of edges - 보행walk 어느 간선도 중복하여 지나지 않는 보행a walk in which no edge is repeated - 경로path vi로 부터 vi로 경로no repeated edge - 사이클cycle

그래프(2/2) v1 v2 v3

트리(1/2) 그래프의 한 종류이다. 사이클을 갖지 않고, 루트라 불리는 특별한 하나의 정점을 가지는 유향 그래프 루트root : one distinct vertex 리프들leaves 부모parent 자식child 레벨level 높이height

트리(2/2) Root Level 0 Height = 3 Leaf Level 3

증명기법(2/2) Proof by induction 몇 개의 특정 사례가 참이라는 사실들로부터 여러 문장들이 참임을 추론해 내는 기법 예) 참임을 증명하고자 하는 문장들의 순서열 P1,P2,… 이 있다고 하고 다음이 성립함을 가정 임의의 k(k>=1)에 대해 P1,P2,…,Pk는 참이다. n>=k인 모든 n에 대해서 P1,P2,…,Pn이 참인 사실이 Pn+1이 참임을 의미하도록 하는 문제 귀납기저 귀납단계 귀납가정

Example 1.5 : 높이가 n인 이진트리의 리프 노드의 총 개수는 최대 2n 임 l(n)  2n Basis l(0) = 1 = 20 Inductive Assumption: l(i)2i For i = 0, 1, …, n Inductive Step : l(n+1) = 2l(n) l(n+1) 2 * 2n = 2n+1

언어, 문법, 오토마타

세가지 기초 개념 언어Languages 문법Grammars 오토마타Automata

언어(1/3) 알파벳 {a, b, c, d} 문자열 {ab, aabb, ccdd} 하나 이상의 심볼들의 유한 집합 알파벳에 속한 심볼들의 유한 길이의 순서열

언어(2/3) w = a1a2…an v = b1b2…bn 접합concatenation : wv = a1a2…anb1b2…bn 전도reverse : wr = an…a2a1 길이length : |w| = n 빈문자열empty string : | | = 0, w = w = w 부문자열substring : w = vu v = 접두부prefix, u = 접미부suffix |uv| = |u| + |v|

언어(3/3) 스타폐포star-closure 양성폐포positive-closure L* = L0 U L1 U L2 …

문법(1/3) 영어 문법 “문장은 명사절(noun phrase)과 술부(predicate)로 구성”

문법(2/3) A boy runs Pascal identifier <sentence> -> <noun_phrase><predicate> <noun_phrase> -> <article><noun> <predicate> -> <verb> Pascal identifier <id> -> <letter><rest> <rest> -> <letter><rest> | <digit><rest> | <letter> -> a|b|…| <digit> -> 0|1|…9

문법(3/3) 문법 G 는 다음의 항으로 정의된다 G = (V, T, S, P) V 는 변수라 불리는 유한 집합의 객체 variables T 는 단말심볼이라 불리는 유한 집합의 객체 terminal symbols S 는 시작변수라 불리는 V의 특별한 원소 start variable P 는 생성규칙들의 유한 집합 productions

문법 문법의 핵심은 생성규칙들 x -> y x는 (V U T)+의 원소 y는 (V U T)*의 원소

Automata Control unit Input file Output Storage

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

응용(1/2) Pascal의 식별자 => 언어 식별자를 위한 문법 영문자로 시작 뒤이어 임의의 개수의 영문자나 숫자의 문자열의 집합 식별자를 위한 문법 <id> -> <letter><rest> <rest> -> <letter><rest>|<digit><rest>| <letter> -> a|b|…|z <digit> -> 0|1|…|9

응용(2/2) 식별자 a0를 유도하는 과정 <id> => <letter><rest> => a <rest> => a <digit><rest> => a 0 <rest> => a 0

유한 오토마타 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

확장 전이함수 *: 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.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 언어 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 사람 늑대 양 양배추 사람 늑대 양 양배추 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’

비결정적 유한오토마타 Nondeterministic Finite Automata

비결정성 ? 컴퓨터 => 결정성

비결정적 인식기 각 상황에서 유일한 이동만을 규정하기 보다는 가능한 여러 가지 이동들의 집합을 허용하는 것. 오토마타의 전이 함수가 상태들의 집합을 치역으로 갖게 함으로써 가능해진다.

비결정적 인식기 F : S1 S2 domain range a a a S1 S2

정의 2.4 비결정적 유한 인식기 또는 NFA는 다음과 같이 5 원소 쌍으로 정의 된다. M = (Q, , , q0, F), 여기서 Q, , , q0, F 는 결정적 유한 인식기에서와 같이 정의되나, 함수 : Q  (  {})  2Q

DFA와 NFA의 차이점 치역 NFA에서 전이함수의 인수로 허용 NFA에서는 집합 (qi, a)가 공집합을 허용 NFA에서 의 치역이 멱집합 2Q 내에 있고, 그 값이 Q의 단일 원소가 아닌 Q의 부분집합 NFA에서 전이함수의 인수로 허용 입력 심볼을 읽지 않고도 전이가 가능함 NFA에서는 집합 (qi, a)가 공집합을 허용 특정 상황에 대하여 정의된 전이가 없을 수 있음

그림 2.8 a a q1 q2 q3 a q0 a a q5 q4 a

NFA의  함수 input 1 state q0 {q0, q3} {q0, q1} {q2} q1  {q2} q2 {q2}  1 state q0 {q0, q3} {q0, q1} {q2} q1  {q2} q2 {q2}  q3 {q4} q4 {q4} {q4}

그림 2.9 q0 0,1 1 q1 q2 

정의 2.5 확장전이 함수 전이그래프에서 qi로부터 qj로의 보행이 존재 * (qi, w)가 qj 를 포함 모든 qi, qj  Q와 w  * 에 대해서도 성립

*(q1, a), *(q2, ) *(q1, a) = {q0, q1, q2} *(q2, ) = {q0, q2} *(q2, aa), *(q0, a)

Definition 2.6 nfa M = (Q, , , q0, F) 에 의해서 인식되는 언어 L은 승인되는 문자열들의 집합으로 다음과 같이 정의된다. L(M) = {w  *: *(q0, w)  F  }. 즉, 이 언어는 전이 그래프의 초기 정점에서 종료 정점까지 라벨이 w인 보행이 존재하는 모든 문자열 w들로 구성된다.

Why Nondeterminism? 게임 프로그램 한 시점에서 여러가지 가능한 해들이 존재 최적의 해를 찾는 방법 모든 가능한 해들을 수행해보고 그 결과 중 최적을 찾음 Backtracking 등의 기법을 이용 Nondeterminism은 이러한 문제를 쉽게 풀수 있도록 도와줄 수 있다. Nondeterminism은 복잡한 언어를 간결하게 기술하기에 매우 적합한 방법이다.

결정적 유한 인식기와 비결정적 유한 인식기의 동치성

동치 정의 2.7 L(M1)=L(M2) 즉, 두 오토마타가 같은 언어를 인식하는 경우 두 개의 유한 인식기 M1과 M2는 동치라 한다.

{(10)n : n >= 0} 0,1 q0 q1 q2 1  0,1 1 q0 q1 q2 1

인식 DFA는 NFA의 한 제한된 종류이다. DFA에 의해 인식되는 언어는 어떤 NFA에 의해서도 인식될 수 있다. ???

동치인 DFA는 같은 문자열을 읽어들인 후 명확히 한 상태에 놓이게 된다. 인식 DFA NFA NFA가 문자열 w를 읽은후 그 NFA가 정확히 어느 상태에 있는지 알수 없다 그러나 NFA가 놓여질 수 있는 가능한 상태들의 집합은 Non-terminal임을 알 수 있다. 동치인 DFA는 같은 문자열을 읽어들인 후 명확히 한 상태에 놓이게 된다. 존재

예제 2.12 다음 NFA와 동치인 DFA를 구성 => DFA의 각 상태의 라벨이 NFA의 상태들의 집합이 되도록 각 상태에 라벨을 부여 b q1 q0 q2 a  a

DFA의 전이 ({q0},a)={q1,q2} ({q0},b)= ({q1,q2},a)={q1,q2}  a DFA의 전이 ({q0},a)={q1,q2} ({q0},b)= ({q1,q2},a)={q1,q2} ({q1,q2},b)={q0}

정리 2.2 언어 L이 비결정적 유한 인식기 MN = (QN, , N, q0, FN) 에 의해 인식되는 언어라고 하면, 다음을 만족하는 결정적 유한 인식기 MD = (QD, , D, q0, FD) 가 항상 존재한다. L=L(MD)

정점 {q0}를 갖는 그래프 GD를 생성. 이 정점을 초기 정점으로 한다. 2. 모든 간선이 생성될 때까지 반복 의 어떤 원소 a  에 대해서 진출 간선을 갖지 않는 GD의 정점 {qi,qj,…,qk}를 선택 *(qi,a), *(qj,a),…, *(qk,a)들을 계산 계산된 *들의 합집합을 구하여 이를 {ql,qm,…,qn}라 함 GD에 라벨이 {ql,qm,…,qn}인 정점이 존재 않는다면 이를 추가함 GD에 정점 {qi,qj,…,qk}로부터 정점{ql,qm,…,qn}으로 향하는 간선을 추가하고 이에 라벨 a를 부여

3. GD의 상태들 중 라벨이 qf  FN을 포함하는 모든 상태들을 종료 상태로 지정 4. 인식기 MN이 를 인식하는 경우, GD의 정점 {q0}를 종료 정점으로 지정

예제 2.13 1 q1 q0 q2 0,1 0,1

*({q0},0)U*({q1},0)를 구함=>{q0,q1,q2} 1 q1 q0 q2 0,1 0,1 {q0} 추가 *({q0},0)를 구함 => {q0,q1} {q0,q1}추가 {q0}에서 {q0,q1}로 향하는 라벨 0을 갖는 간선 추가 *({q0},1)를 구함 => {q1} {q1}추가 {q0}에서 {q1}로 향하는 라벨 1을 갖는 간선 추가 *({q0},0)U*({q1},0)를 구함=>{q0,q1,q2} {q0,q1,q2}추가 {q0,q1}에서 {q0,q1,q2} 로 향하는 라벨 0을 갖는 간선 추가

*({q0},1)U*({q1},1)를 구함=>{q1,q2} 1 q1 q0 q2 0,1 0,1 *({q0},1)U*({q1},1)를 구함=>{q1,q2} {q1,q2}추가 {q0,q1}에서 {q1,q2} 로 향하는 라벨 1을 갖는 간선 추가 *({q0},0)U*({q1},0)U*({q2},0)를 구함=>{q0,q1,q2} {q0,q1,q2}존재 {q0,q1,q2}에서 {q0,q1,q2}로 향하는 라벨 0을 갖는 간선 추가 *({q0},1)U*({q1},1)U*({q2},1)를 구함=>{q1,q2} {q1,q2}존재 {q0,q1,q2}에서 {q1,q2}로 향하는 라벨 1을 갖는 간선 추가

10. *({q1},0)U*({q2},0)를 구함=>{q2} 1 q1 q0 q2 0,1 0,1 *({q1},0)를 구함=>{q2} {q2}추가 {q1}에서 {q2} 로 향하는 라벨 0을 갖는 간선 추가 *({q1},1)를 구함=>{q2} {q2}존재 {q1}에서 {q2} 로 향하는 라벨 1을 갖는 간선 추가 10. *({q1},0)U*({q2},0)를 구함=>{q2} {q1,q2}에서 {q2}로 향하는 라벨 0을 갖는 간선 추가

11. *({q1},1)U*({q2},1)를 구함=>{q2} 12. *({q2},0)를 구함=>{} 1 q1 q0 q2 0,1 0,1 11. *({q1},1)U*({q2},1)를 구함=>{q2} {q2}존재 {q1,q2}에서 {q2}로 향하는 라벨 1을 갖는 간선 추가 12. *({q2},0)를 구함=>{} {}추가 {q2}에서 {} 로 향하는 라벨 0을 갖는 간선 추가 13. *({q2},1)를 구함=>{q2} {q2}에서 {q2} 로 향하는 라벨 1을 갖는 간선 추가

1 q1 q0 q2 0,1 0,1 q1을 포함한 모든 상태들을 종료 상태로 지정 정점 {q0}를 종료 정점으로 지정할지 판단

그림 2.16  {q0} 1 {q0,q1} {q1} 0,1 1 {q0,q1,q2} {q1,q2} 1 0,1 {q2} 1 1 {q0,q1} {q1} 0,1 1 {q0,q1,q2} {q1,q2} 1 0,1 {q2} 1  0,1

정규언어와 정규문법 Regular Languages and Regular Grammars

정규언어 임의의 언어 -> 정규 언어 정규언어를 표현하는 보다 정교한 방법이 필요함 => 정규표현 이를 인식하는 유한 인식기의 존재여부 DFA 나 NFA 가 존재해야 함 정규언어를 표현하는 보다 정교한 방법이 필요함 => 정규표현

Relation of RG, RE, Automata Regular Expression Finite Automata Regular Grammars

정규표현 정규언어를 기술하는 한가지 방법이 정규표현 regular expressions 이다. 표기 알파벳 의 문자열, ( ) 연산자 +, . , *의 결합 예) 언어 {a} => 정규표현 a 언어 {a, b, c} => 정규표현 a+b+c

정규표현 + : 합집합UNION . : 접합CONCATENATION * : 스타폐포STAR-CLOSURE (a + b  c) * {a}  {bc} {, a, bc, aa, abc, bca, bcbc, aaa, aabc, …}

정의 3.1  를 주어진 알파벳이라고 하면 정규표현은 1. , , and a  는 모두 regular expressions 이다. 이 들을 기본 정규표현 primitive regular expressions이라 한다. 2. r1과 r2가 정규표현이면, r1+r2, r1. r2, r1*, 과 (r1) 는 모두 정규표현이 된다. 3. 특정 문자열이 정규표현이 되기 위해서는 기본 정규 표현에서 시작하여 위 규칙 (2)를 유한횟수만큼 반복함으로써 그 문자열이 유도될 수 있어야 한다.

정의 3.2 정규표현 r에 의해 묘사되는 언어 L(r)은 다음 규칙들에 의해 정의된다. 1.  은 공집합을 나타내는 정규 표현이다. 2.  는 {}를 나타내는 정규 표현이다. 3. 모든 a   에 대해 a는{a}를 나타내는 정규 표현이다.

정의 3.2 만약 r1과 r2가 정규 표현일 경우 4. L( r1+ r2) = L(r1)  L(r2),

정규표현과 정규언어의 관계 정리 3.1 r 을 정규 표현이라 하자. 언어 L(r) 을 인식하는 nfa가 존재하며, 결과적으로 L(r)은 정규언어이다.

그림 3.1 q1 q0 . nfa accepts   q1 q0 . nfa accepts {} a q1 q0

그림 3.2 . L(r)을 인식하는 nfa의 도식적인 표현 M(r)

그림 3.3 Automaton for L(r1 + r2). M(r1)   M(r2)  

그림 3.4 . Automaton for L(r1r2). M(r1) M(r2)   

그림 3.5 Automaton for L(r1*).  M(r)   

그림 3.6 Find an nfa which accepts L(r), where r = (a + bb)*(ba* + ). . M1 accepts L(a+bb) . M2 accepts L(ba* + ) M1 M2 a a b b b  

그림 3.7 Automaton accepts L((a + bb)*(ba* + ))  M1 M2  a    b b 

정규언어와 정규문법

NFA에 대한 정규 표현 찾는 방법 NFA의 모든 보행에 대한 라벨 생성 어렵다 전이그래프에 사이클 존재 -> 몇번 반복할 지 모름 기록 문제로 해결

정규언어에 대한 정규표현 일반전이 그래프Generalized transition graph 간선의 라벨에 정규 표현을 부여하는 전이 그래프 라벨은 여러 정규표현들의 접합 <= 그 자체도 정규 표현이 된다. a -> a a, b -> a + b

예제 3.8 L(a* + a*(a + b)c*) a c* a + b

그림 3.9 e d c qj qi q b a ce*b ae*d ce*d qj qi ae*b

그림 3.12 a EE OE a b b b b a OO EO a

그림 3.12 aa bb a ba OO EE OE EE a ab b b b b b a a b a OO EO EO a

그림 3.12 aa bb ba a(bb)*a OO EE aa+ab(bb)*ba ab b+a(bb*)ba EO b EE a a

정규언어 묘사방법 NFA DFA 정규표현 간단한 문법을 이용 => 정규문법

Relation of RG, RE, Automata Regular Expression Finite Automata Regular Grammars

정규문법

우선형 문법과 좌선형 문법

문법 문법 G 는 다음의 항으로 정의된다 G = (V, T, S, P) V 는 변수라 불리는 유한 집합의 객체 variables T 는 단말심볼이라 불리는 유한 집합의 객체 terminal symbols S 는 시작변수라 불리는 V의 특별한 원소 start variable P 는 생성규칙들의 유한 집합 productions

정의 3.3 문법 G = (V, T, S, P)에서 모든 생성규칙들이 다음의 형태를 갖는 경우 이를 우선형 right-linear문법이라 한다. A -> xB, A -> x, 여기서 A, B V 이고 x  T*이다. 문법의 생성규칙들이 모두 다음의 형태를 갖는 경우 이 문법을 좌선형 left-linear 문법이라 한다. A -> Bx, A -> x. 정규문법은 우선형 문법이거나 좌선형 문법이다.

예제 3.12 우선형 문법Right-linear 문법 G1 = ({S}, {a,b}, S, P1)에서 생성규칙 P1이 다음과 같이 주어졌다면 S -> abS | a r = (ab)*a

예제 3.12 좌선형 문법Left-linear 문법 G2 =({S, S1, S2}, {a,b}, S,P2) 에서 생성규칙 P2가 다음과 같이 주어졌다면 S -> S1ab, S1 -> S1ab | S2, S2 -> a r = (a(ab)*)

예제 3.13 문법 G = ({S,A,B}, {a,b}, S, P)가 다음과 같은 생성규칙들을 갖는 경우 이는 정규 문법이 아니다. S -> A, A -> aB|, B -> Ab 선형문법 linear grammar은 각 생성규칙의 우변에 하나 이하의 변수만 있을 수 있으며, 이 변수의 위치에는 제한이 없는 문법을 말한다. 정규문법 선형문법

우선형 문법 => 정규언어 정규언어 => nfa 우선형 문법에 대한 정규언어 우선형 문법 => 정규언어 정규언어 => nfa

정리 3.3 G = (V,T,S,P) 가 우선형 문법 right-linear grammar 이면 L(G)는 정규 언어이다. 증명 V={V1,V2,…} S=V0 생성규칙 : V0->v1Vi, Vi->v2Vj,…

정리 3.3 문자열 w가 L(G)에 속한다면 문법 G의 생성규칙들의 형태로 볼때 그 유도과정은 다음과 같을 것이다 V0 => v1Vi => v1v2Vj => v1v2…vkVn => v1v2…vkvl = w

그림 3.15 a1 a2 . . . am Vi Vj Represents Vi ->a1a2 … am Vj => *(Vi,a1a2…am) = Vj a1 a2 . . . am Vi Vf Represents Vi -> a1a2 … am => *(Vi,a1a2…am) = Vf

연습문제 1 다음 문법에 의해 생성되는 언어를 인식하는 유한 오토마타를 구성해 보자. S -> aS | aA A -> bA| b L = {anbm | n, m  1}

정규언어 => dfa dfa => 우선형 문법 정규언어에 대한 우선형 문법 정규언어 => dfa dfa => 우선형 문법

정리 3.4 L 이 알파벳 에 대한 정규 언어일 때, L = L(G)를 만족하는 우선형 문법 G=(v, , S, P)가 항상 존재한다.

정리 3.4 증명 언어 L을 인식하는 dfa를 M=(Q, , , q0, F)라하고, Q={q0, q1, …, qn} 이고  = {a1,a2,…,am}이라 가정 dfa M으로부터 V={q0, q1, …, qn} S=q0

정리 3.4 w  L(G)를 보임 M에 존재하는 각 전이에 대해 (qi,aj)=qk 문법 G의 P에 다음과 같은 생성규칙 추가 qi -> ajqk qk  F인 경우에는 P에 다음 생성규칙 추가 qk ->  w  L(G)를 보임

오토마타 M이 dfa가 아니어도 가능함

정리 3.5 언어 L이 정규언어이고 그럴때만 L = L(G)인 좌선형 문법 G가 존재한다. 증명 A->Bv A->v L(G)=(L(G’))R A->vRB A->vR

정리 3.6 언어 L이 정규언어이고 그럴때에만 L = L(G)를 만족하는 정규문법 G가 존재한다.

Theorem 3.1 Let r be a regular expression. Then there exists some nondeterministic finite accepter that accepts L(r) Consequently, L(r) is a regular language.

Theorem 3.2 Let L be a regular language. Then there exists a regular expression r such that L = L(r)

그림 3.15 Regular expressions Theorem 3.2 Theorem 3.1 dfa or nfa Regular grammars