계정: 로그인
AA

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

§ 1.3 Regular Expressions