CSC 473
Instructions:
Fuduo Cheu Name________________________________
Midterm 1
• You may use your text and your OWN notes for this exam but you may not use anything else.
• Your work MUST be your own. Consulting with anyone or searching the Internet is cheating and
if you are caught you will get a zero.
• Please write legibly and answer each question completely.
• You may print out this exam to fill in, or you may read it from a terminal and write your answers
on a separate piece of paper. Either way you must create a pdf of your answers and submit them to GradeScope by 2:00 PM.
1
1. (15 pts) a.
b.
Construct a state diagram for a DFA that accepts the following language: {w ∈ {0, 1}*: |w| is odd}
→嶕
Construct a state diagram for a DFA that accepts the following language:
-{w ∈ {0, 1}*: w ends with an 10} 李德。
Construct the state diagram for a product DFA from the answers from parts a and b
to create声a DFA that accepts {w ∈ {0, 1}* : |w| is odd or w ends with an 01} 燮(IMPORTANT: construct a “product” DFA not any DFA that gives the set)
c.
2
2. (5ipts) Construct the state diagram for a DFA which accepts the following language: {w ∈ {1, 0}* : w contains at least two 0’s not followed by a 1}
3. (5 pts) Give the state diagram with no more than 11 states for an NFA which recognizes the language: L = {w ∈ {a,b,c}* : w contains at least one substring that contains the same element three times in a row} (e.g. bcaaab ∈ L, bbb ∈ L, aabaabb ∉ L) Bonus point if your NFA has less than 11 states.
-※ _ –
”
-_- -_-
䛧
3
4.
i. 厱
Q
(10 pts) Convert the following NFA to a DFA using the method demonstrated in class. Draw the state diagram. You don’t need to show (or calculate) the states that are not reachable
from the start state.
23
QQ QQ
Q
Q
ǙIO
to Úo
4
5. (4 pts) For each of the languages defined by the following regular expressions, give two strings that are members and two strings that are not members. (Σ = {a, b})
a. ba ⋃ ab*a
m em bersiba.ab.ba
b. (∅* ⋃ b)b hotmembersiab.abamembe.rs:0/,bhotmembers:a,ab
6. (5 pts) Give a regular expression that generates the following language: {w ∈ {a, b}* : w does not contain the substring aab}
7. (4 pts) Let D be a DFA. What simple property of D is true iff ε ∈ L(D)
8. (4 pts) Use the alphabet Σ = {0,1} for this problem:
a. List all the languages that can be recognized by a DFA with 1 state.
ta-DisregularlanguageO.IO
b. List all the languages that can be recognized by an NFA with 1 state.
1,E
,
5
9. (10 pts) Use the method learned in class to convert the DFA below to a Regular Expression. Be sure to show all your work.
0→l eaub-fto.ES-
a.
First draw the GNFA to start the process
0 kti
→2
b.
0-1 2-lroirowro.ruxr.EDU
管… …
Now Eliminate State 1 and draw the new GNFA
EQlavb): aub
,
r.Mr.io/UEQE=Q=r23Urzir.*rn=4U(avb)QE=avb-o-o-@ro3=rosU
c. Now come up with the resulting regular expression
rozr.hr2 3 = (avb)*
6
10. (10 pts) Prove that the set {wwR: w ∈ {0, 1}*} is not a regular language. (Recall wR is the reverse of w)
A s s u m e A i s R . L .t n
P.L .is
Psost.V-WEA.IWIZPW-xyzs.t.l.IXYIEP2.ly
3.xyizEA.tiletw-OPOIPaudNK4BPletv-XYZS.tn
3
conditionsholdlxykp-sxy-ok-syidlylso-sjsoxy0EOPJPOP.SE
⺕
170
11. (10 pts) (a) Where is the error in the following proof? (b) Correct it or state briefly why it cannot be corrected.
Choose w = (01)p ∈ L and |w| = 2p ≥ p cond3i.AiswtR.L.info
L = {(01)n n ≥ 0} is not a regular language.
Pf: (by contradiction) Assume it is regular. Let p be the pumping length.
Write w = xyz. Where x = 0, y = 1, and z = (01)n-1
|xy| = 2 ≤ p and |y| = 1 > 0
but xy0z = 0(01)n-1 ∉ L
but, by Pumping Lemma xz ∈ L =><= (contradiction) Therefore, L is not a regular language.
7
12. (10 pts) Answer the following True or False:
a. L = {w ∈ {0, 1, . . ., 9}* : w has no leading zeros and when viewed as a decimal
number is a prime number between 1 and 1000} . (This means 2 ∈ L, 13 ∈ L but 25 ∉ L) L is a regular language.
Fdse
b. Suppose A and B are regular languages then {w: w = xy where x ∈ A and y ∈ B} is a regular language.
True
c. If a language is not regular then it is uncountable.
d. If N is an NFA with n states then ∃ a DFA D with not more than n2 states such that L(N) = L(D) .
e. Let L = {a, aab, aaabb, b, aa}. There is no DFA with 5 states that recognizes L.
13. (8 pts) Suppose we define a variation of an NFA as follows: ExamNFA is a 5-tuple
(Q, Σ, δ, q0, F) that accepts x ∈ Σ* if every possible state that it could be in after reading
input x is a state from F. (In other words, an ExamNFA is just like an NFA except that an NFA accepts x if some state that it could be in after reading input x is in F, and an ExamNFA accepts x if every state that it could be in after reading input x is in F).
a. Show if L is a Regular Language, then ∃ an ExamNFA M such that L(M) = L. (your answer can be brief)
Falseirueirw-imacuptsxEtizanMS.t.LI/nkLcMhas5-tnpk(QE
b. Show that if M is an ExamNFA, then L(M) is a regular language
,勺,9。F),
theretoreUMlisareg.hr
8、 layuage