Automata and Theory of Computation 20160304정리

한양대학교 ocw Automata and Theory of Computation 20160304 강의를 정리

Finte Automata

DFA(Deterministic Finite Acceptor)

$$M=(Q,\sum,\delta,q_0,F)\\Q:set of states\\ \sum: input \ alphabet \\ \delta :Q \times \sum \rightarrow Q: transition \ function \\ q_0 \in Q : initital \ state \\ F \subset Q : final states \\ $$

example

$$M=(\{g_0,g_1,g_2\},\{0,1\},\delta,q_0,\{q_1\})\\ \delta(g_0,0)=g_0 \\ \delta(g_0,1)=g_1 \\ \delta(g_1,0)=g_0 \\ \delta(g_1,1)=g_2 \\ \delta(g_2,0)=g_2 \\ \delta(g_2,1)=g_1 $$

각각의 경우에서 전부 정의

transition graph

$${\delta}^*(g_0,11)=g_2 \\ \delta(\delta (g_0,1),1)=g_2$$

$$L(M)= \{w \in {\sum}^*: \delta^*(g_0,w) \in F \}$$

initial state부터 transition 했을시에 final state에 도달하는 string => DFA에 accept 되는 string

example

$$\{a^n b,n>=0\} \\ q_2 \ is \ trap \ state $$

ab
$$g_0$$$$g_0$$$$g_1$$
$$g_1$$$$g_2$$$$g_2$$
$$g_2$$$$g_2$$$$g_2$$

example

sol => ab …..

example

001이 들어있지 않은 문자를 accept 하는 DFA를 구하라

001을 accept하는 DFA는 아래와 같음

001을 accept하는 DFA

0,0,1을 final로 바꿈으로 만들 수 있음

001이 들어있지 않은 문자를 accept 하는 DFA

댓글을 남겨주세요~