CISC 5200—Computer Language Theory Thursday 5 March 2020
MIDTERM EXAMINATION (SOLUTIONS)
PROBLEM POINTS 1 /20 2 /15 3 /20 4 /10 5 /10 6 /10 7 /15 8 /10
TOTAL / 100
Copyright By PowCoder代写 加微信 powcoder
1. Answer the questions as well as you can.
2. Partial credit will be given, so show your work where appropriate and be precise. In particular, make sure that your answers to Pumping Lemma questions are clear enough that I can tell that your reasoning is correct.
3. The total number of points on this exam is 110 points, but it will be graded on a 100-point basis. Extra credit!!
4. You will be allowed to bring one double-sided U.S.letter-size (8 12 × 11-inch) sheet of notes with you to the exam.
5. You will not be allowed to use any electronic devices during the exam (laptops, tablets, phones, calculators).
Thought for the day: A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.
Problem 1. ( / 20 points)
Answer the following true/false and fill-in-the-blank questions. For this question, I do not need to see any work; I
merely need to see your answers.
(a) An NFA 𝑁 accepts a string 𝑤 iff when 𝑤 is presented to 𝑁, all paths terminate in an accept state. False
(b) A DFA always halts on its input. True
(c) Let 𝐿 be a regular language. Then 𝐿 is pumpable via the pumping lemma for regular languages. True
(d) Let 𝐿 be a language that is pumpable (via the pumping lemma for regular languages). The 𝐿 is a regular language. False
(e) Regular languages are closed under complementation. True
(f) It is impossible to build a DFA that recognizes { x𝑛y100000x𝑛 : 𝑛 ≥ 0 }. True
(g) Deterministic and nondeterministic finite automata have equivalent expressive power. True
(h) Deterministic and nondeterministic PDAs have equivalent expressive power. True
(i) A CFG 𝐺 is ambiguous if some string generated by 𝐺 has more than one leftmost derivation.
(j) If a language can be described by a PDA, then it is a
language. context-free
Problem 2. ( / 15 points) Let 𝑀 be a DFA given by the diagram
𝑞0 𝑞1 𝑞2 𝑞3 a,b
(a) [7 points] Provide a formal description of 𝑀. 𝑀 = {𝑄, Σ, 𝛿, 𝑞0, 𝐹}, where
• 𝑄={𝑞0,𝑞1,𝑞2},
• Σ={a,b,c},
• 𝐹={𝑞3},and
• the transition function 𝛿: 𝑄 × Σ → 𝑄 is given by
𝛿abc 𝑞0 𝑞1 𝑞0 𝑞0
𝑞1 𝑞4 𝑞2 𝑞4 𝑞2 𝑞4 𝑞4 𝑞3 𝑞3 𝑞3 𝑞3 𝑞3 𝑞4 𝑞4 𝑞4 𝑞4
(b) [4 points] In plain English, describe the language 𝐿(𝑀) described by this DFA. To get full credit, you need to provide a reasonably succinct description that ignores irrelevant details. Complete the sentence below (my solution is less than ten words long).
The DFA shown above describes a language that . . . whose first a is followed by bc
(c) [4 points]) Give a regular expression that describes this language.
(b ∪ c)∗abc(a, b, c)∗
Problem 3. ( / 20 points)
For each of the languages described below, the alphabet Σ is {a, b, c}. For each part below, follow the instructions, which will have you draw a DFA, draw an NFA, or provide a regular expression. When writing regular expressions, you may use the Σ symbol.
(a) (5 points) Let 𝐿1 be the language consisting of all strings in Σ∗ of length at least 2 that begin and end with different symbols. Draw the state diagram for a DFA that recognizes 𝐿1.
(b) (5 points) Let 𝐿2 be the language consisting of all strings in Σ∗ containing the substring ab. Draw the state diagram for an NFA that recognizes 𝐿2.
(c) (5 points) Let 𝐿3 be the language consisting of all strings in Σ∗ that do not contain the substring ab. Draw the state diagram for an NFA that recognizes this language.
The simplest thing to do is draw a DFA for 𝐿3′ , and then switch the roles played by the accepting and nonaccepting states, getting
(d) (5 points) Draw the state diagram for an NFA that recognizes 𝐿2 · 𝐿3. a,b,c a,b,c a,b,c
𝑞0 𝑞1 𝑞2 𝑞3 𝑞4 𝑞5 𝑞6
Problem 4. ( / 10 points)
Give context-free grammars that generate the following languages. Each of these can be done using only one non-
terminal symbol and one rule (of course, the rule must use the | symbol, or there will be infinite recursion). (a) {a𝑚bc𝑛 :𝑚,𝑛≥0}.
𝑆 → 𝜀 | a𝑆𝜀 | 𝑆b
(b) {a2𝑛b2c4𝑛 :𝑛≥0}. 𝑆 → b2 | aa𝑆cccc
Problem 5. ( / 10 points)
Let 𝐺 = (𝑉, Σ, 𝑅, 𝐸) be a grammar, with 𝑉 = {𝐸, 𝑇, 𝐹} and Σ = {a, +, ∗, −, /, (, )}, having the rules
𝐸 → 𝑇+𝐸 | 𝑇−𝐸 | 𝑇 𝑇 → 𝐹∗𝑇 | 𝐹/𝑇 | 𝐹 𝐹 → (𝐸) | a
(a) [7 points] Give the leftmost derivation for a/a/a. We have
𝐸 → 𝐹 → 𝐹/𝑇 → a/𝑇 → a/𝐹/𝑇 → a/a/𝑇 → a/a/𝐹 → a/a/a
(b) [3 points] Within 𝐿(𝐺), which of the following is true? (i) a−a−a=(a−a)−aNo
(ii) a−a−a=a−(a−a)Yes
Note: I really meant to put / signs, rather than − signs. In that way, the answer for part (b) would’ve followed easily from that of part (a). However, what I had intended to put here and what actually appeared here are analogous; the main point is that with this grammar, the operations are right-associative, rather than left-associative.
Problem 6. ( / 10 points)
Prove that context-free languages are closed under the concatenation operator. You must prove this using “proof by
construction” using a CFG.
Let𝐿1and𝐿2beCFLs;wanttoshowthat𝐿1·𝐿2isalsoaCFL.Since𝐿1and𝐿2areCFLs,forthat𝐿𝑖 =𝐿(𝐺𝑖).We need to construct a new CFG 𝐺 that generates the language 𝐿1 · 𝐿2. Let 𝑆1 and 𝑆2 be the start variables for 𝐺1 and 𝐺2. Let 𝑆 be a new variable, not found in 𝑉1 ∪ 𝑉2. Choosing
𝐺 = (𝑉1 ∪ 𝑉2 ∪ {𝑆′}, Σ1 ∪ Σ2, 𝑅1 ∪ 𝑅2 ∪ {𝑆 → 𝑆1 | 𝑆2}) we have 𝐿(𝐺) = 𝐿1 · 𝐿2, as required.
Problem 7. ( / 15 points) Let𝐿={a𝑚b𝑛c𝑚 :𝑚,𝑛≥0}.
(a) (5 points) Is 𝐿 regular? (Simple “yes” or “no” answer.) No.
(b) (10 points) Prove your answer to part (a). If you said the language was regular, you should be able to provide a proof by construction; if you said that it was not regular, you should be able to prove it non-regular by using the pumping lemma.
Suppose that 𝐿 were regular. By the Pumping Lemma, there is a pumping length 𝑝 such that any string 𝑠 of length at least 𝑝 obeys the three conditions of the Lemma. Choose 𝑠 = a𝑝bc𝑝. Decompose 𝑠 = 𝑥𝑦𝑧 as per the Pumping Lemma. Since |𝑥𝑦| ≤ 𝑝 and |𝑦| > 0, we see that 𝑦 is a nonempty string of a’s. Thus the string 𝑥𝑦𝑦𝑧 has more b’s than a’s, and hence 𝑥𝑦𝑦𝑧 ∉ 𝐿, contradicting the Pumping Lemma.
Problem 8. ( / 10 points)
Let𝐿={a𝑖b𝑗c𝑘b𝑗a𝑖 :𝑖,𝑗,𝑘≥0}.Provethat𝐿iscontext-freebyinformallydescribingaPDAthatrecognizesthis
while next char is a, push(a).
while next char is b, push(b).
while next char is c, read (and ignore) it. while next char is b
if stack top is b then pop else reject while next char is a
if stack top is a then pop else reject
if stack is empty and all string chars processed then accept else reject
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com