Compiler 강의 노트 CH5

Finite state autmata

Finite state automaton

• FSA is an abstract model of a computing machine
• FSA is a directed graph, vertex representing state.
• Just remember primitive memory(current state)

---

FSM is a low-level machine

• It has only states.
• No memory
• No outputs

---

DFA M is denpted by

Q : finite states
Sigma : input alphabet
delta : Set of transition functions
q0 : The initial state
F : Set of final states

q0 is one if the states, All the states can be final states.
DFA is a acceptor for string.

example)

Find equivilant RE for this DFA

example)

example)

{w (={0,1}* | w include 111}

example)