제 3장. Regular Languages 와 Regular Grammars 학습목표 Finite Automata 이외에 Regular Language를 표현하는 방법으로 Regular Expression과 Regular Grammar에 대해 학습하고 3가지가 동일함을 이해한다
Concise but important practical applications 개요 Concise but important practical applications
Regular Expressions RE의 기본 정의에 대해서 알아보자 그렇다면 주어진 RE가 나타내는 언어는 무엇인가?
RE이 나타내는 언어 상식적인 간단한 정의!
RE이 나타내는 언어: 예 좀 연습이 필요합니다 반대는 어렵다 0으로 끝나는 경우 1로만 된 경우
RE: Homework (Exercises 3.1) 4 : n과 m 각각이 짝수인 경우와 홀수인 경우로 나누면… 9 : 세가지 case로 나누어서 생각해 봅시다. 14 : 쉬운 문제부터 어려운 문제로 나갑니다. 할 수 있는 만큼만. 22, 23 : 응용문제
Connection between RE and RL Generating labels of all walks from q0 to any final state λ λ a λ λ prove by induction on no. of operators
Finding NFA for L(r): 예 λ a b Regular Expressions Regular Languages : easy!! 그 반대는 : Find RE capable of generating labels of all the walks from q0 to any final state : book keeping problem (existence of cycles) 새로운 표현법이 필요하겠군!
RE RL: GTG 이용 (1) a+b c* a RL GTG 변환 RE e qi qj d a q b c ce*d neither final nor initial e qi qj d a q b c ce*d qi qj ce*b ae*d ae*b
RE RL: GTG 이용 (2) 복잡해 보이지만 단순 변환과정을 실수 없이 하는 연습이 필요함 이와 equivalent한 GTG로 변환해가면서 최종 GTG를 얻음 q0 r1 qf r4 r3 r2 prove by induction on no. of states in GTG q0 a q1 b a,b q2 ab*b q0 a+b b+ab*a q2
RE의 응용 예 state reduction
RE/RL: Homework (Exercises 3.2) 4 (a), (b) : 쉽지만 끈기를 필요로 하는 변환문제 10 : NFA로 부터 RE구하기 연습 17 : 그냥 생각만 해보고 실제로 하지는 말 것. 매우 어려운 문제!
Regular Grammars : RG RL NFA
Regular Grammars: 예 not regular
RG RL 증명 Right-linear grammar의 derivation을 표현하는 NFA 구축 V0 V1 Vf b a
DFA Grammar RG RL 증명 (1) state variable symbol terminal
RG RL 증명 (2) Left-linear grammar인 경우는 어떻게 될까?
총정리 증명 RE Regular language를 표현하는 방법 DFA or NFA DFA’s, NFA’s RG 1 2 3 4 Regular language를 표현하는 방법 DFA’s, NFA’s Regular expressions Regular grammars Power면에서 동등
RG : Homework (Exercises 3.3) 1, 2 : 가장 typical한 기계적 변환 연습 9 : left-linear grammar의 연습