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

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

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

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

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

4 Three Basic Concepts(1/2)
Languages Grammars Automata

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

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

7 Three Basic Concepts(2/2)
Languages Grammars Automata

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

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

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

11 계산이론개요

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

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

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

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

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

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

18 오토마타 1 q1 q0 q2 1 1

19 그래프 (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

20 그래프(2/2) v1 v2 v3

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

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

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

24 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

25 언어, 문법, 오토마타

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

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

28 언어(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|

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

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

31 문법(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

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

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

34 Automata Control unit Input file Output Storage

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

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

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

38 유한 오토마타 Finite Automata

39 Automata Control unit Input file Output Storage

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

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

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

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

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

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

46 그림 2.1 1 q1 q0 q2 1 1

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

48 언어와 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}

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

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

51 증명 가정 : 길이가 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까지의 보행이 존재한다는 것을 의미한다.

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

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

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

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

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

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

58 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’

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

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

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

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

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

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

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

66 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}

67 그림 2.9 q0 0,1 1 q1 q2 

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

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

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

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

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

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

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

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

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

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

78 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}

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

80 정점 {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를 부여

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

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

83 *({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을 갖는 간선 추가

84 *({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을 갖는 간선 추가

85 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을 갖는 간선 추가

86 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을 갖는 간선 추가

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

88 그림 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

103 그림 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  

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

105 정규언어와 정규문법

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

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

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

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

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

111 그림 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

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

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

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

115 정규문법

116 우선형 문법과 좌선형 문법

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

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

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

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

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

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

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

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

125 그림 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

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

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

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

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

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

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

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

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

134 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.

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

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