제 4 장. Regular Language의 특성

Presentation on theme: "제 4 장. Regular Language의 특성"— Presentation transcript:

1 제 4 장. Regular Language의 특성
학습목표 정규언어의 일반적 특성에 대해 이해하고, 주어진 언어가 regular인지 판별하는 방법 학습  Closure Property & Pumping Lemma

2 개요 정의→표현→유용성→특성? Every formal language is regular? accepts by some complex finite automaton? ① operations on RL : set operations, changing operations, closure question ② ability to decide on certain properties : finite or not? ③ regular language or not? DFA, RE, RG 할 수 있는 일, 없는 일 no 다양한 language 집합의 분별도구 general properties를 만족하나?

3 Closure Properties : Set Operations (1)
한 두개의 instance가 아닌 모든 원소의 특성을 설명하기 위한 방법 Closure Properties : Set Operations (1) 예) RL is closed under union ① closure under simple set operations RL is closed under union, intersection, concatenation, complementation, star-closure Thm pf: Intersection은?  좀더 복잡함!

4 Closure Properties : Set Operations (2)
 Constructive proof의 또 다른 등장, 여러 곳에서 유용!

5 Closure Properties : Reversal
단순히 증명만을 원한다면 이걸로… Thm RL : closed under reversal 단순한 set operation이외에 좀더 복잡한 연산에 대한 closure 특성이해 필요

6 Closure Properties : Homomorphism (1)
② Closure under other operations : homomorphism, right quotient Def 1:

7 Closure Properties : Homomorphism (2)
Pf: Thm

8 Closure Properties: Right Quotient (1)
기본정의가 좀 이해하기 어려우려나? Def 2: ① take all strings in L1 having a suffix belonging to L2 ② for the string, removing this suffix belongs to L1/L2 q0 a,b a b q1 q3 q5 q2 q4

9 Closure Properties: Right Quotient (2)
증명도 좀 해보고… Thm Pf:

10 Closure Properties: Right Quotient (3)
증명의 마무리! Closure Properties: Right Quotient (3) 따라서, 는 regular!

11 Closure Properties: Right Quotient (4)
예를 가지고 이해해 봅시다 예) 3 1 2 a,b b a

12 Closure Properties: Exercises 4.1
2 : constructive proof를 이용한 NFA의 구축 6 : 집합의 특성을 이용해볼 것 10 : Right quotient를 제대로 이해하고 있는지 체크하는 쉬운 문제 15 : Right quotient의 응용능력 (left quotient)… 그리 쉽지만은 않을 걸… 20 : 이런 류의 문제를 접해본다는 의미이상은 없음

13 여기서 잠깐만: Wordsworth로부터
My Heart Leaps Up My heart leaps up when I behold A rainbow in the sky; So was it when my life began; So is it now I am a man; So be it when I shall grow old, Or let me die! The Child is Father of the Man; And I could wish my days to be Bound each to each by natural piety. 무지개 하늘의 무지개 바라보면 내 가슴 뛰노라. 내 삶이 시작될 때 그러했고 어른이 된 지금도 그러하니 늙어서도 그러하리라. 아니라면 죽음만도 못하리! 어린이는 어른의 아버지 원컨대 내 생애의 하루하루가 자연에 대한 경애로 이어지기를.

14 Elementary Questions about RL
Thm 1 Thm 2 Thm 3

15 Elementary Questions : Exercises 4.2
5 : palindrome이 regular인가?  일단 DFA를 만들어 보고… 9 : 좀 어려운 문제지만, 이것도 일단 DFA를 만들어 보고… 12 : 약간의 트릭이 필요하긴 한데, 뒤에 답안이 있군!

16 Identifying Nonregular Languages
language is regular only if the information that has to be remembered at any stage is strictly limited Pigeonhole Principle If put n objects into m boxes, n>m then at least one box must have more than one item in it 상자의 수보다 더 많은 공을 넣어야 한다면? 어딘가 1개 이상의 공이 들어가는 상자가 있을 수밖에!

17 Nonregular Languages: 예
예) pf) 대강은 이해할 수 있겠는데, 이를 좀더 정형화한 틀이 필요하지 않을까?

18 Finite한 상태로 infinite한 스트링을 표현하자니 어쩔 수없이 어떤 상태는 한번 이상 사용될 수밖에 없겠죠!
Pumping Lemma (1) 그것이 바로 펌핑 렘마!!! Idea : in a transition graph with n vertices, any walk of length n or longer must repeat some vertex (contain a cycle) Thm Finite한 상태로 infinite한 스트링을 표현하자니 어쩔 수없이 어떤 상태는 한번 이상 사용될 수밖에 없겠죠!

19 Pumping Lemma (2) 그걸 한번 증명해 봅시다 Pf

20 Pumping Lemma: 예 pumping lemma holds for every w∈L & every i
증명도 증명이지만 이를 다양한 문제에 적용할 수 있어야 함 예) pumping lemma holds for every w∈L & every i → if it is violated even for one w or i, then language cannot be regular

21 Pumping Lemma: 예예 closure property to show that L is not regular
그 밖의 여러 문제들…  진득한 연습, 또 연습 Pumping Lemma : holds for every w∈L and every i 예)

22 Pumping Lemma : Exercises 4.3
4 (b), (d), (f) : pumping lemma의 적용능력 함양문제 8 : pumping lemma의 직접적인 적용은 좀 어려울 듯. 답은 … false 9 (a), (c), (e) : 정규언어에 대한 직관을 키울 수 있는 문제들. 15 : finite 언어와 infinite 언어의 차이… 자, 이제 시험을 통해 regular language를 총 복습해 보고, 그 다음 단계의 언어인 context-free language로 넘어가 봅시다!!!  잊지맙시다. 9/29 시험일… 4장까지…