True/False (12 points)
Recommended lime: b minutes
If an NFA accepts a language L
• then you can generate
Copyright By PowCoder代写 加微信 powcoder
an NrA that accents
complement of language L by swapping the accept and non-accept
You can build a DFA to recognize the language L = O’Om
Recuse DFAs cannot have edges that handle the empty string. espilon (E).
therefore a DFA can never accept the empty string E.
The language of binary strings with more O’s than I’s is a regular language.
Every Context Free Language is a Regular Language
Regular languages are closed under Union. Concatena
ton, and Complement.
Short Answer Ouestions (24 points).
kecommended lime: 10 minutes
Provide the regular expression that describes the language L of binary strings that contains exactly
two Us or at least one 1. You
mav use E where 2=0 U 1. (6 points)
What is the minimum
pumping length for the binary language represented by 10*? (3 points)
Provide/describe one language L that is Context Free but not Regular (4 points)
Which of the following best describes the language L= (01)”? Circle only one answer. (3 points)
The language is not regular and not context free
The language is not regular but is context free
The language is regular and is not context free
The language is regular and is context free
c. Let R be the start symbol of a CFG that generates language L1, and let Q be the start symbol of a
CFG that generates language L2. (8 points)
i. Provide a CFG rule with start symbol S that generates language Ll U L2 using R and Q
Provide a CFG rule using start symbol S that generates
Let L be the language of binarv strings that end with “Ol”.
Cample strings in L: 01, 001, 101, …,
Draw a DFA that accepts L (9 points)
Draw an NFA that accepts L. Use ‘NFA thinking” and use the minimum number of states and
edges (e.g., you will not receive any credit if you use the solution from part a). (6 points)
(13 points) Convert the following NFA into a DFA. Do not simplify the DFA. Ree. Time: 10 minutes
(12 points) Provide Context Free Grammars (CFGs) that generate each of the following 2
languages, L.
Recommended limo: 8 minutes
Hint: I personally find it helpful to first write out the regular expression for L first.
L contains all binary strings that start and end with at least two l’s or start and end with
at least three 0’s. (6 points)
Some strings in L: 11011, 1111, 000000. 000010000, 00011 1 1 100000
b. L is all binary strings where the O’s come before any 1’s. (6 points)
Some strings in L: 01, 0001, 000, 11, E
6. (10 points) Use the pumping lemma to prove that the following language is not regular:
(Sample strings in L: abbb, aabbbb, aaabbbbb, …) Rec. Time: 4 minutes
Here is the pumping lemma
IfI is a regular language, then there is a number p where if s is any string in L of at least p,
then s may be divided into three parts s-xyz, satisfying the following conditions:
1. for each i 20, xy’z E L
3. /xy/ ≤p
Fam Part 2: Post-Midterm Material (Recommended maximum time 65 minutes)
(10 points) Let L
= a'”b” n> 1. which includes strings: aaab, ananabb,.
.. Intormallv describe the PDA
that accepts this language
You can describe it in English/pseudocode, ideally with numbered steps (nc
need tor a state diagram). Make sure you cover all cases
Recommended lime: 7 minutes
2. True/False Questions (16 points)
The Halting problem is Turing Recognizable.
Recommended Time: 8 minutes
b. If a language L is decidable, it must be in P.
c. AT is Turing Recognizable.
All languages are recognized by some Turing Machine.
c. The 8-Clique problem is in both P and NP.
All problems that are in P or NP are decidable.
g. If A is reducible to B, then A can be harder than B (B can be easier than A).
h. With a working nondeterministic TM, CLIQUE can be solved in polynomial time.
True False
True False
3. (9 points) Describe the language L recognized by the PDA below, using either English or set notation.
Recall that the notation a, b -› c means that when input a is read then the value b on the top of the stack is
replaced with c.
Multiple answer questions-circle all true statements. (19 points). Recommended time: 15 minutes
Circle all of the following statements about TMs that are truc. (5 points)
A 4-Tape Turing machine can recognize or decide more languages than a 1-Tape TM
A non-Deterministic TM can recognize or decide more languages than a deterministic TM
A 2-Tape TM can solve problems more quickly than a 1-Tape TM.
A deterministic TM can recognize and decide every language that a PDA with non-
determinism can recognize and decide.
We consider a non-deterministic TM to be a reasonable model of a computer.
b. Circle all the statements about recognizability and decidability that are true. (2 points)
Every language that is Turing Decidable is Turing Recognizable.
Every language that is Turing Recognizable is Turing Decidable,
Every language that is not Turing Decidable will not be Turing Recognizable
iv. Every language that is not Turing Recognizable will not be Turing Decidable.
Circle all languages L that a TM can recognize. (3 points)
i. L= 0010
L= ww” (a palindrome)
iv. L=abc ixj=k
Circle all of the following machines that may not halt when processing an input string (2 points)
i. Non-Deterministic Turing Machine
iv. Deterministic Turing Machine
Based on what we learned in class about how to compare the sizes of infinite sets, circle all of
the statements that are true. (3 points)
There are more integers than even integers
There are more real numbers than natural numbers.
There are more rational numbers than natural numbers.
iv. The number of real numbers is countable.
The number of natural numbers is countable.
Circle all of the following machines that can recognize the language O”I° in O(n) time. (4 points)
iv. 2-tape TM
Short answer questions- write 1-2 sentences. (17 points).
Kecommended time: 10 minutes
(4 points) Advanced aliens land on Earth and provide you with one technology that you
dreamed of: a machine that will tell you
assume that this actually
if any Turing Machine M will halt on any input w
say it will do. One
ol your fends from
Computation class says that this means that P = NP and therefore that all NP-complete problems are
in P. Is your friend smart or confused? Briefly justify your answer.
(4 points) Finding whether a number is prime in polynomial time is quite difficult and a method
for doing this was only discovered recently.
Therefore there must be an error with the
following simple solution (and there is!). Describe the problem. Here is the simple solution:
To see if a number n is prime, we only need to check whether any integer between 2 and at
most n/2 divides evenly into it. Checking whether a number goes in evenly is simple and can
be done in polynomial time. Given that there are at most n/2 things to check, and given that
each step is in polynomial time, therefore this simple algorithm runs in linear time and hence
runs in polynomial time.
Everything in the previous paragraph is correct, except the last part “therefore this simple
algorithm runs in linear time and hence runs in polynomial time.” What is the issue? This may
seem tricky but we covered this precise question, and the underlying issue, in class. Hint: In class
I said most students will forgot about this issue.
(3 points) Precisely describe in one sentence what it means for language L to be Turing
recognizable without using the term “recognize” in any of its forms.
d. (3 points) Precisely describe in one sentence what it means for language to be Turing
decidable without using the term “decide” in any of its forms.
C. (3 points) ADrA represents a language. Describe this language by describing the elements
that are in the language.
points) Reduction of 3SAT to CLIQUE. Given the propositional 3at logic formula F below, reduce
it to the CLIQUE problem by drawing a graph G such that the formula is satisfiable if and only if there is
a k-clique in G. You must also specify the value of k. So, draw the graph G below and list the value of k.
Note that the – is the complement symbol, which is equivalent to having the bar over the variable. Also
recall that a k Clique is a subgraph with k nodes where each of the k nodes are directly connected to the
others k-1 nodes. Recommended time: 7 minutes.
F= (VI V VI v V2) A (-VIv -V2 V -V2) ^ (-VI V V2 V V2)
(10 points) Describe, in words, a 1-tape Turing Machine that decides the language 0° 120 2″, where n is O
or greater (i.e., will accept strings with equal numbers of O’s and 2’s and twice as many I’s as 0’s or 2’s,
with the O’s coming before the I’s which come before the 2’s– and will reject otherwise). I suggest you
provide a set of numbered steps. Recommended time: 8 minutes.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com