20132 건국대 계산이론 수업의 숙제를 정식으로 게시하여 공지하기 전에 숙제 내용을 편집하며 교정하기 위한 작업용 문서.
회차: 1차
공지일: 9/27(금)
제출 기한: 10/04(금) 강의 시간 미정
제출 방식: 문제와 답을 종이에 (인쇄하지 말고) 손으로 직접 써서 강의 시간에 제출
§ 0.2 Mathematical Notions and Terminology
Set
Let A be the set {x, y, z} and B be the set {x, y}.
What is A ∪ B?
What is A × B?
What is 2^{B}, that is, the power set of B?
Graph
Consider the undirected graph G=(V,E) where V, the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}.
Draw the graph G.
 What are the degrees of each node?
Indicate a path from node 3 to node 4 on your drawing of G.
§ 1.1 Finite Automata
The formal description of a DFA M is ({q_{1}, q_{2}, q_{3}, q_{4}, q_{5}}, {u, d}, δ, q_{3}, {q_{3}}), where δ is given by the following table. Give the state diagram of this machine.

u 
d 
q_{1} 
q_{1} 
q_{2} 
q_{2} 
q_{1} 
q_{3} 
q_{3} 
q_{2} 
q_{4} 
q_{4} 
q_{3} 
q_{5} 
q_{5} 
q_{4} 
q_{5} 
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.
{w  w begins with a 1 and ends with a 0}
{w  w contains at least three 1s}
{w  w contains at least two 0s and at most one 1}
 The empty set
 All strings except the empty string
§ 1.2 Nondeterminism
Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.
The language {0} with two states
The language {w  w contains the substring 0101 (i.e., w = x0101y for some x and y)} with five states
The language 0^{*}1^{*}0^{+} with three states