[이산수학] 정규언어, 정규표현

<< 이산수학 11주차 >>

Finite State Automaton 
A = (Q, ∑, δ, q0, F)
- DFA    δ : Q x ∑ -> Q
- NFA    δ : Q x ∑ -> 2^Q // 멱집합(다음 상태가 없거나, 또는 여러 개)

NFA는 사람에게 편하다 -> 컴퓨터 DFA로 변환할 수 있다.
(=> 두 오토마타가 인식하는 스트링 집합은 동일하다.)

Subset Contrauction algorithm : NFA -> DFA
- Q^d = 2Q                                      //상태 집합
- ∑^d = ∑                                         //입력 기호 집합
- q0^d = {q0}                                   //초기 상태
- F^d = {S∈Q^d | S∩F≠공집합}       // 승인 상태 집합
- δ^d : Q^d x ∑ -> Q^d는 상태 전이 함수이다.  // 상태 전이 함수

NFA를 DFA로 변환하시오
1) NFA 표 그리기
2) DFA 표 그리기
3) 오토마타 그리기
>> 시작 상태는 동일 & accept state는 동일
 하지만 시작 상태에서 도달할 수 없는 unreachable한 상태가 존재한다. -> 이런 곳들은 삭제



정규 언어?
: 정규 언어, 정규 문법(type3), 유한 상태 오토마타(A), 정규 표현(r)과의 관계
 >> 추가된 부분은 정규 언어를 정의할 때 사용하는 정규 표현(r)이다. 
       L = L(G) = L(A) = L(r) 이다.
- 제약이 많고
- 표현력이 낮고
- 기계처리가 쉬움
- id/pw에서 쓰임

정규 표현(Regular Expression)
: 기호 집합인 ∑로 만들 수 있는 정규 표현의 r의 구문이다.
- 기호 λ는 정규 표현이다.
- ∑에 속한 기호들은 정규 표현이다.
- r가 정규 표현이라면 r*도 정규표현이다.
- r1과 r2가 모두 정규 표현이라면, r1|r2도 정규 표현이다. >> 선택
- r1과 r2가 모두 정규 표현이라면, r1r2도 정규표현이다. >> 결합
- r가 정규 표현이라면, (r)도 정규표현이다. >> 괄호

Q. ∑={a,b}으로 만들 수 있는 정규 표현의 예는?
A.  a aa* a|b* (a|b)*bb

우선순위
1) 괄호 ()
2) 반복 *
3) 결합 
4) 선택 |

Q. 처리 순서
 (a|b)*bb >> ((((a)|(b))*b)b
 a|bc* >> (a)|((b)(c*))

정규 집합
: Syntax and semantics(구문 및 의미론)
- 구문 <- 정규표현
- 시멘틱스 <- 문자열 집합

정규 표현 r에 의미하는 스트링 집합을 L(r)이라고 부르면, 계산 방식은
- L(λ) = {λ}
- L(a) = {a}
- L(r*) = (L(r))*
- L(r1|r2) = L(r1)∪L(r2)
- L(r1r2) = L(r1)L(r2)

 a|bc*의 스트링 집합
 L(a|bc*) = L(a)∪(L(bc*)) = L(a)∪(L(b)L(c*)) = {a}∪({b}{ε c c^2 c^3 c^4 ... }) = {a}∪({b bc bc^2 bc^3 bc^4 ... })
= {a, b, bc, bc^2, bc^3, bc^4, ... })

L(a*(a|b)*bb) >> ∑={a,b}의 ∑*를 구한 것과 동일하다.
즉, a가 n번 출현하고, 이어 a 또는 b가 출현하는데 마지막은 bb로 끝나는 언어이다.



정규 표현 r이 의미하는 스트링 집합 L(r)을 정규 언어라고 한다.
정규 표현이 존재한다.
L1 = {(a^m)(b^n) | m>0 n>0} // aa*bb*
L2 = {(b^m)(a)(b^n) | m,n>0} // 만약 여기서 m, n>=0이라면 a*b*이다.
★L3 = {(a^n)(a^n) | n>0}★
// b와 c가 쌍을 이루어야 하나, 기억 개념이 없기 때문에 정규 표현이 존재하지 않는다. 

1*|01 >> L(1*|01) = L(1*)∪L(01) = L(1*)∪L(0)L(1) = {1}*∪{01]



정규 문법과 유한 상태 오토마타
//정규 문법에서 유한 상태 오토마타로
N = {S, C}
- S는 시작 상태
- T= {a, b}
- P= {S->bS, S->aC, C->bC, C->b}

//유한 상태 오토마타로부터 정규 문법으로
G = (N, ∑, P, S)
N = {E, O}, P={E->aO, E->bE, O->aE, O->bO, O->λ}, S=E, T={a,b}

//유한 상태 오토마타로 인지할 수 없는 언어
- L = {0ⁿ1ⁿ | n=0,1,2 ... }
 왜 아닐까? 유한한 상태인데, b도 그만큼 매칭을 시켜줘야 하지만 매칭을 시키지 못한다.

//오토마타 도치
: L이 정규 언어라면, 이것을 도치한 언어도 정규언어이다.
 L^R = {an ... a2 a1 | a1 a2 ... an ∈ L}
=> 이 경우에 오토마타는 초기상태를 accept상태로, accept상태를 초기 상태로 보내면 가능해진다.
  (+승인 상태가 여러개일 경우)

오토마타 도치

//오토마타 여집합
 - ∑* \ L | = 오토마타의 여집합  -> 정규 언어
A = (O, ∑, δ, q0, F)에서 L=L(A)라면, A의 여집합 = (Q, ∑, δ, q0, Q\F)이다.
accept 된 것은 reject로, reject는 accept상태로 맞교환하면 여 오토마타를 구할 수 있다.

//오토마타 교집합
 L1 ∩ L2 = L(A1 ∩ A2)이다.  -> 정규 언어

오토마타 교집합

//오토마타 합집합
 L1 ∪ L2 = L(A1 ∪ A2)이다.  -> 정규언어

오토마타 합집합

type 3
>> 정규언어는 정규 표현(정의), 정규 문법(생성), 유한 상태 오토마타(승인)를 가짐.
-------------------------------------------------
tpye0
>> 튜링 머신
-------------------------------------------------
type 2(CFG)
>> 문맥 자유 언어, C, JAVA와 같이 BNF 형식으로 나타낸다.

type2(CFG)를 한번에 치환(parallel)하도록 확장시킨 것이 L-grammar이다.

Turtle Graphics
- terminal symbols : ∑
  go/left,right/repeat 숫자/program, end

<program> ::= Program <command list>
<command list> ::= <command>*end
<command> ::= <repeat command> | <primitive command>
<repeat command> ::= repeat <number> <command list>
<primitive command> ::= go|right|left
<number> ::= 1|2|3|4|5|6|7|8|9|


L-Grammear
: 프렉탈 그래픽에서 사용한다.

- 우리가 여태 했던 것은 Sequential rewriting의 치환이었다.  // 순차적
- 이것을 확장하면 병렬치환이 가능해진다.                               // 한 번에
- 프렉탈 그래픽 생성을 위한 린덴메이어 L문법
- CFG와 거의 비슷하나, 문법만 다르다. => P는 A->B 형식의 생성 규칙  // 한 번에 바꿔라 

L-System
Parallel rewriting system G=(V,S,P)

- Koch curve 
Variables = {F}
Constants = {+,-}
rules = {F->F+F-F-F+F}

- Sierpinski triangle
Vaibles = {A,B}
Constants = {+,0}
Start = A
Rules = [A->B-A-B, B->A+B+A}

각각의 모습이 전체 모습으로 이뤄진다. => 프렉탈