[作業] 自動機與形式語言 林智仁教授
Due date: 10/17
1.14
a. Show that, if M is a DFA that recognizes language B, swapping the accept
and nonaccept states in M yields a new DFA that recognizes the complement of
B. Conclude that the class of regular languages is closed under complement.
b. Show by giving an axample that, if M is an NFA that recognizes language C,
swapping the accept and nonaccept states in M doesn't necessarily yield a new
DFA that recognizes the complement of C. Is the class of languages recognized
by NFAs closed under complement? Explain your answer.
1.15
Give a counterexample to show that the following construction fails to prove
Theorem 1.49, the closure of the class of regular languages under the star
operation. Let N1=(Q1,Σ,δ1,q1,F1) recognize A1. Construct N=(Q1,Σ,δ,q1,F)
as follows, N is supposed to recognize A1*.
a. The states of N are the states of N1.
b. The start state of N is the same as the start of N1.
c. F={q1}∪F1.
The accept states F are the old accept states plus its start state.
d. Define δso that any q belongs to Q and any a belongs to Σε.
δ(q,a)= δ1(q,a) q not belongs to F1 or a!=ε
δ1(q,a)∪{q1} q belongs to F1 and a=ε
1.16 (b)
Use the construction given in Theorem 1.39 to convert the following two
NFA to equivalent DFA
(see the graph in p.86)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.32
→
10/08 12:46, , 1F
10/08 12:46, 1F
※ 編輯: htl 來自: 140.112.30.32 (10/08 16:59)