Finite automata and regular languages

- overview

 실제 컴퓨터가 너무 복잡하니까, 계산이론 모델로 추상화하자!

 가장 단순한 모델로 시작 ~   finite automata / finite automaton

 

  *  finite automata - good model but limited amount of memory

  * finite automata --> pushdown automata (* stack) --> turing machine (*stack, tree)

 

▶ Example - controlling a toll gate / an automatic door 

▶ DFA : Deterministic finite automata

▷ definition 

 - set of state

 - rules ( transition function)

 - alphabet (set of symbol)

 - start state (only one)

 - accept states (at least 1)

 

▷ formal definition : 5-tuple ~ M=(Q,Σ,δ,q,F)

 - Q : state

 - Σ : alphabet 

 - δ : Q ×Σ→ Q : transition function

 - q : start state

 - F : accept states

 

▷ transition function δ

  - if the automaton is in state x when it reads a 1, it then moves to state y
   => δ(state, symbol) = next state  ==> δ(x,1) = y

 

▷  language of M -- L(M)

   - finite automaton -- M

   - language of a finite automaton 

    : r0 = q

    : ri+1 = δ(ri,wi+1), for i = 0,1,... n-1

    : if rn ∉ F, then we say that M rejects w

    : if rn ∈ F, then we say that M rejects w

    :: w may be the empty string(ℇ) ~ length : 0(zero)

    :: start state 가 accept state 일때만 empty string 인식할 수 있음

 

- L(M) = {w : w is a string over ∑ and M accepts w }

     * a language A is called regular, 

if there exists a finite automaton M such that A = L(M)

 

▷ ∑* includes the empty string ℇ
  (참고) : dfa에서 ℇ는 NO INPUT

▷ entended transition function 
  δ' : Q ×Σ* → Q 

  - δ' (r, w) :

    w 가 empty string 일 때 δ(r,w) = r

    w 가 va일 때(a는 알파벳에 포함) = δ(δ'(r,v),a)

 

▶ Regular operations --- regular language 에 대해서

▷ union              : binary-oper

▷ concatenation  : binary-oper

▷ star --- empty string도 가능 --- unary-oper

 

▷ closed property 

  : regular language 는 위의 세 개의  regular operation에 대해 닫혀있다.

 

▶ NFA : Nondeterministic finite automata

▷ several choices may exist for the next state at any point
▷ How to compute

 - 1. splits into multiple copies ...

 - 2. tree
 

▷ state diagram에 accept되는 path가 하나라도 있으면 accept!

▷ Definition 차이 
  - empty string 도 next state로 갈 수 있게 함!

  - δ : Q ×Σε → P(Q)
* 만약  δ(r,a)=∅ ~ M은 더이상 진행할 수 없고, 계산은 hang상태가 됨
 

▷ w = 01ℇ011 
   - string 길이 : 5

   - symbol 개수 : 6

▶ Equivalence of DFAs and NFAs
  - NFA에서 accept되는 language만이 DFA에서 accept된다. (필요충분, vice versa)

  * how to convert DFA to NFA

▷ DFA to NFA
 - function 정의 
   δ'  : Q ×Σε → P(Q) 

      a 가 empty string --> ∅

      a 가 empty string 아닐때 ---> δ(r,a)
▷ 바꾸는 방법 2가지! 숙지하기
 

▶ DFA minimization

  - key point : 도달 안되는 state, 중복되는 state ~ remove!

  - approach 
    1) Bottom-up

    2) Top-down 

    - 숙지!

 

▶ Closure under the regular operations

▷ 책보고 theorem 증명 연습 열심히 해야 함...

 

▶ Regular expressions

- language 묘사할 때 r.e 사용

- string pattern 묘사에 강력한 방법!
 

▶ Equivalence of regular expressions and regular languages 

R.E = F.A = R.L ... 다 같닼
▷ converting a DFA to a Regular Expression
 

▶ The pumping lemma and non-regular languaes

▶ Higman's Theorem