Account:

2013-2 건국대 계산이론 수업숙제를 정식으로 게시하여 공지하기 전에 숙제 내용을 편집하며 교정하기 위한 작업용 문서.

회차: 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 AB?

• What is A × B?

• What is 2B, 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 ({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}), where δ is given by the following table. Give the state diagram of this machine.

 u d q1 q1 q2 q2 q1 q3 q3 q2 q4 q4 q3 q5 q5 q4 q5

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