계정: 로그인
AA 📝
Draft

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}.

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}}.

§ 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}.

§ 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}.

§ 1.3 Regular Expressions