Finite Automata

• Computing Machines with a FINITE number of STATES

• state: internal (내부적인) representation

• input: external (외부적인) influences on the system

• state에 input이 가해지면 다른 state로 넘어간다. → FINITE AUTOMATA

• set of strings accepted by an automation A: ”launguage” of A, L(A) ex. L(Tennis): 승자 정해지는 모든 string

Ex. Tennis Scoreboard Automata

• Rules

  • match = 3~5 sets ( 5판3선 )
  • set = 6개 이상의 games
  • to win, at least 4 points
  • to win, 2점 이상 차이 나야 함 (듀스와 어드밴티지 존재)
  • inputs:
    • s ( server scores )
    • o ( opponents scores )

• Transition Diagram:

  

  final은 원 두개이다.

  ex. input = s o s o s o s o s o s s output: server wins → L(Tennis)에 속함

  

  ex. input = o o o o output: opponent wins → L(Tennis)에 속함

  ex. input = o o o o s ? 이미 끝났는데 들어오니 state 의미 없다 → L(Tennis)에 속하지 않는다

• Naming each state

  • xssoo에서 x는 승리 여부, ss는 서버의 점수, oo는 상대의 점수이고 input 1: 서버 득점, input 0: 상대 득점이라면 다음과 같이 나타낼 수 있다:

    

  • state transition table 다음과 같이 작성할 수 있다.

  

  • Circuit ROM을 사용해서 구현할 수 있다(디시설 참고)

    Sequential Logic

  

Types of Finite Automata

DFA(Deterministic Finite Automata)

On each input, automaton moves onto one and only one state 한번에 다른 하나의 상태로만 전이한다.

• Accept/reject finite strings of symbols

• produce: Unique computation of automaton for each input string

• cover EVERY State on EVERY Alphabet symbol 모든 알파벳에 대한 output이 있어야 한다.

  • →dead state 추가 필요. ex. 위에서 게임 끝나고 나서 s,o 들어오면 dead!

    

• DFA is Quintuple(5-tuple): M= (Q,SIGMA, delta, q_0, F)

  • Q: finite set of states
  • SIGMA: Input alphabet
  • sigma: transition function, Q × SIGMA → Q (도메인= Q와 SIGMA 곱집합)
    • arguments
      • state
      • input symbol
    • sigma(q,a):= state that the DFA goes to, when state q; input a
  • q0 in Q: start State
  • F in Q: a Set of final,accepting states

  ---

  Quintuple example

  

  ---

  Transition Diagram Example

  problem:

  

  diagram:

  

  ---

  Another Example

  diagram:

  

  Transition Table:

  

  Extended Transition function: 모든 state에서 word input에 대한 행동을 정의한다.

  

  • basis: sigma hat (q, epsilon) = q

  • induction: sigma hat (q, wa) = sigma(sigma hat(q,w), a)